Мирко нужно купить землю, чтобы построить дом для своей семьи. Он присмотрел K участков. Для простоты будем считать, что участок представляет собой поле с N строками и M столбцами, N × M клеток в сумме.

Мирко знал, что до начала строительства участок надо поддерживать в порядке. По этой причине он приобрёл газонокосилку. Для покоса участка ему нужно проехать по каждой клетке поля хотя бы раз. Он может начать с любой клетки, смотря в одно из четырёх основных направлений (вверх, вниз, влево или вправо). Его газонокосилка может двигаться только вперёд (перемещаться в следующую клетку вдоль текущего направления) или поворачиваться на 90 градусов. К тому же, ради безопасности, Мирко может косить только на своём участке, не выходя за пределы поля.

Так как поворачивать газонокосилку непросто, Мирко хочет минимизировать количество поворотов газонокосилки. Для каждого из K участков земли ему нужно знать минимальное число поворотов для покоса. Помогите Мирко с этой задачей.

Как известно, в июне во Флатландии будет проходить чемпионат Юпитера по футболу. В турнире примут участие n команд, а сам турнир будет разыгран в один круг, в ходе которого каждая команда сыграет с каждой другой командой.

На Юпитере выпускают футбольную форму m цветов. Каждая команда привезёт с собой два комплекта формы различных цветов. Разумеется, во время матча все игроки одной команды должны быть одеты в форму одного цвета, отличного от цвета формы другой команды.

Для судейства всех матчей этого чемпионата был приглашён глава Фантастической Инопланетной Футбольной Ассоциации Йозеф. Перед началом матча Йозеф назначает каждой из команд цвет футболок, в которых игроки выйдут на поле. Разумеется, выбирать можно только из тех двух цветов футболок, которые привезла с собой команда. После этого Йозеф выбирает себе футболку какого-то цвета, отличного от обоих цветов, в которых будут играть команды. Таким образом, обе команды и судья будут находиться на поле в футболках разного цвета. Любую футболку и команды, и Йозеф могут использовать в неограниченном количестве игр чемпионата.

Футболки для судейства Йозеф закупает непосредственно перед чемпионатом, опираясь на знание о цветах футболок, привезённых командами на турнир. Поскольку Йозеф экономит деньги своей федерации, он хочет купить себе минимальное количество футболок, такое что их хватит для обслуживания всех матчей. Данная задача слишком сложна для обычного футбольного судьи, поэтому он обратился за помощью к вам.

Хранители в опасности, и Доктор Манхэттен со своим другом Дэниелом Драйбергом должны срочно их предупредить. Всего в команде хранителей n человек, i -й из которых находится в точке плоскости с координатами ( x _i , y _i ) .

Как всем известно, доктор Манхэттен вычисляет расстояние между двумя хранителями i и j по формуле | x _i - x _j | + | y _i - y _j | . Дэниел, как обычный человек, считает, что расстояние равно .

Сейчас успех операции зависит от того, сколько существует пар ( i , j ) ( 1 ≤ i < j ≤ n ), таких что расстояние между хранителем i и хранителем j , вычисленное Доктором Манхэттеном, равняется расстоянию между ними, вычисленному Дэниелом. Вычислить эту величину попросили именно вас.

Олег пришел посмотреть на зеркальный лабиринт. Зеркальный лабиринт представляет собой комнату \(n\) на \(n\), у которой каждая клетка или пуста, или содержит зеркало, соединяющее диагональные концы соответствующей клетки. Зеркала в таком лабиринте обладают почти идеальной способностью отражать свет, что создаёт интересные визуальные ощущения и способствует потери ориентации в пространстве.

Олег по натуре очень любопытен, поэтому он решил установить на южной стороне лабиринта \(n\) лазеров, направленных внутрь лабиринта. На северной стороне лабиринта Олег установил \(n\) приёмников, тоже направленных внутрь лабиринта. Пронумеруем лазеры и приёмники с запада на восток от \(1\) до \(n\). Для каждого лазера известен номер приёмника, в который он должен попасть. Так как в один приёмник не могут попасть одновременно два лазера, то эти номера образуют перестановку — каждый из номеров приёмников встречается ровно один раз.

Вы пришли в лабиринт вместе с Олегом. Помогите ему расставить зеркала в изначально пустом лабиринте так, чтобы максимальное количество лазеров попали туда, куда они должны. За пределами лабиринта зеркал нет, так что если лазерный луч покидает пределы лабиринта, то он не сможет вернуться назад.

Назовём палиндромом непустую строку, которая читается одинаково справа налево и слева направо. Например, « abcba », « a » и « abba » являются палиндромами, а « abab » и « xy » не являются.

Назовём подстрокой строки строку, полученную отбрасыванием некоторого (возможно, нулевого) количества символов с начала и с конца строки. Например, « abc », « ab » и « c » являются подстроками строки « abc », а « ac » и « d » не являются.

Назовем палиндромностью строки количество её подстрок, которые являются палиндромами. Например, палиндромность строки « aaa » равна \(6\), так как все её подстроки являются палиндромами, а палиндромность строки « abc » равна \(3\), так как только подстроки длины \(1\) являются палиндромами.

Вам дана строка \(s\). Вы можете произвольным образом переставлять символы в ней. Требуется получить строку, имеющую максимальную палиндромность.