Биологи Карельского Мутационного Проекта (КМП) недавно решили начать новые исследования, которые должны доказать, что люди — близкие родственники мамонтов. Чтобы доказать это странное предположение, ученые планируют сравнить ДНК людей и мамонтов.

Для сравнения ДНК разделяется на фрагменты длины n и они последовательно сравниваются. Поскольку в процессе развития у людей и мамонтов могли происходить мутации, предлагается следующий способ сравнения фрагментов.

Рассмотрим строку α. Будем говорить, что α мутирует в β, если α = xyz для некоторых (возможно пустых) x, y и z, а β = xy^Rz, где y^R означает строку y, записанную задом наперед (например, "abc"^R = "cba"). Будем говорить, что строки α и β похожи, если α может быть превращена в β не более чем за 4 мутации.

По двум данным фрагментам ДНК определите, похожи ли они.

Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

• cut — разрезать граф, то есть удалить из него ребро;
• ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Охотник Боб часто гуляет со своей собакой Ральфом. Боб гуляет с постоянной скоростью и его путь – ломаная (возможно, самопересекающаяся), каждая вершина которой задается двумя целыми числами (X_i, Y_i) – декартовыми координатами.

Ральф бегает сам по себе, но обязательно должен встречаться с хозяином в указанных N точках. Собака начинает свой путь одновременно с хозяином в точке (X₁, Y₁) и завешает его вместе с хозяином в точке (X_N, Y_N).

Ральф может бегать с любой скоростью, не превышающей в два раза скорость Боба. Пока Боб идет по прямой из точки в точку, собака ищет деревья, кусты, холмики и прочие интересные места, которые заданы парами целых чисел (X^'_j, Y^'_j). Всего таких мест M. Тем не менее, покидая своего хозяина в точке (X_i, Y_i) (где 1 ≤ i ≤ N), Ральф посещает не более одного интересного места перед тем, как опять встретить хозяина в точке (X_i + 1, Y_i + 1).

Ваша задача – найти маршрут, удовлетворяющий указанным выше условиям, с максимальным количеством посещаемых интересных мест. Он представляется ломаной, по которой бегает Ральф. Ее вершинами должны быть все точки (X_i, Y_i) и посещенные интересные места (X^'_j, Y^'_j). Последние должны быть посещены (то есть встречаться в описании пути) не более одного раза.

Пример пути Боба (сплошная линия), набора интересных мест (точки) и одного из лучших путей Ральфа представлены на рисунке:

У Егора очень старый телефон. Слава отправил Егору кодовую фразу от Серёжиного банковского счёта, чтоб его ограбить, но телефон Егора настолько стар, что не умеет принимать длинные сообщения. Он разбивает их на несколько маленьких случайной длины, и приходят они ему в случайном порядке.

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