Язык программирования

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

Две бесконечные равномерные прямоугольные решётки заданы размерами ячеек x₁ y₁ и x₂ y₂. Решётки расположены на плоскости параллельно друг другу и координатным осям так, что смещение одного из узлов второй решётки относительно узла первой составляет Dx по горизонтали и Dy по вертикали. В результате наложения образуется новая, "составная" решётка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решётки.

Ограничения: 1 <= x₁, y₁, x₂, y₂ <= 100, 0 <= D_x < x₁, 0 <= D_y < y₁, все числа целые.

Входные данные
В первой строке находятся числа x₁, y₁, x₂, y₂, D_x, D_y, разделённые пробелами.

Выходные данные
В первой строке вывести N - количество получившихся площадей, в следующих N строках - сами площади.

Гирлянда состоит из N лампочек на общем проводе. Один её конец закреплён на заданной высоте A мм (H₁ = A). Благодаря силе тяжести гирлянда прогибается: высота каждой неконцевой лампы на 1 мм меньше, чем средняя высота ближайших соседей (H_i = (H_i - 1 + H_i + 1) / 2 - 1 для 1 < i < N). Требуется найти минимальную высоту второго конца B (B = H_N) при условии, что ни одна из лампочек не должна лежать на земле (H_i > 0 для 1 <= i <= N).

Ограничения: 3 <= N <= 1000 - целое, 10 <= A <= 1000 - вещественное.

Входные данные
В первой строке находятся два числа, N и A.

Выходные данные
Вывести одно вещественное число B с двумя знаками после запятой.

Строку Фибоначчи F(K) для натуральных чисел K определим так: F(1) = 'A', F(2) = 'B', F(K) = F(K - 1) + F(K - 2) при K > 2, где "+" означает конкатенацию строк. Требуется найти количество вхождений строки S, состоящей из символов A и B, в строку Фибоначчи F(N).

Ограничения: длина S от 1 до 25, 1 <= N <= 45.

Примечание. Длина F(45) равна 1 134 903 170.

Входные данные
В первой строке содержится число N, во второй - строка S.

Выходные данные
Выводится одно число - количество вхождений строки S в строку Фибоначчи F(N).

Дана матрица A размером N*N, заполненная неотрицательными целыми числами. Расстояние между двумя элементами A_{i j} и A_{p q} определено как |i - p| + |j - q|.

Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.

Ограничения: 1 <= N <= 200, 0 <= A_{i j} <= 1 000 000.

Входные данные
В первой строке содержится число N. Затем идут N строк по N чисел, разделённых пробелами и представляющих собой матрицу.

Выходные данные
Выводится N строк по N чисел, разделённых пробелами, - модифицированная матрица.

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

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

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

Входные данные
В первой строке находятся два целых числа, N и M, разделённые пробелом: N - число файлов на сервере, M - число сообщений, посланных клиентами, пытающимися определить полное имя файла.

Каждая из следующих N строк содержит одно полное имя файла. Полное имя файла дано в стиле, аналогичном формату 8.3 MS-DOS. Каждое полное имя представлено в форме имя.расширение, где и имя, и расширение состоит только из заглавных латинских букв и цифр. Имя всегда имеет от одного до восьми символов. Расширение имеет до трёх символов и может быть пусто. Если расширение пусто, разделяющая точка может быть опущена.

Каждое полное имя файла появляется во входном файле не более одного раза.

1 <= N <= 1000, 1 <= M <= 100.

Выходные данные
В первой строке выводится число файлов-кандидатов для данных набора файлов и числа сообщений между клиентами. Выводится 0, если файлы-кандидаты отсутствуют.

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

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

Входные данные
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= N <= 1000.

Выходные данные
Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Вывести квадрат, состоящий из NxN ячеек, заполненных числами от 1 до N² "змейкой" (см. примеры).

Входные данные
В первой строке находится единственное число N. 2 <= N <= 100.

Выходные данные
Выводится N строк по N чисел, разделённых пробелами. Не допускаются начало змейки в другом углу или другое её направление.

Вывести квадрат, состоящий из N*N клеток, заполненных числами от 1 до N² по спирали (см. примеры).

Входные данные
В первой строке находится единственное число N. 2 <= N <= 100.

Выходные данные
Выводится N строк по N чисел, разделённых пробелами. Не допускается начинать спираль в ином, кроме верхнего левого, углу, закручивать спираль против часовой стрелки или изнутри наружу.

Даны 5 целых чисел. Среди них:
* если одинаковы 5, то вывести "Impossible", иначе
* если одинаковы 4, то вывести "Four of a Kind", иначе
* если одинаковы 3 и 2, то вывести "Full House", иначе
* если есть 5 последовательных, то вывести "Straight", иначе
* если одинаковы 3, то вывести "Three of a Kind", иначе
* если одинаковы 2 и 2, то вывести "Two Pairs", иначе
* если одинаковы 2, то вывести "One Pair", иначе
* вывести "Nothing".

Входные данные
В первой строке находятся 5 чисел через пробел. Все числа от 1 до 13 включительно.

Выходные данные
Выводится одна строка - результат анализа.

В текстовом редакторе Microsoft Word имеется достаточно мощный механизм поиска и замены, который доступен после установки флажка Подстановочные знаки (Use wildcards). При этом некоторые символы в строке поиска получают особый смысл.

Так, знаком вопроса в шаблоне поиска можно задать ровно один любой символ. Кроме того, в шаблоне поиска на месте одного из символов в квадратных скобках можно перечислить сразу несколько символов, никак их при этом не разделяя (поиск будет считаться успешным, если на этом месте стоит один из символов, указанных в [ ]). В квадратных скобках можно вместо любого символа указывать и диапазоны символов. Мы будем использовать только три следующих диапазона: 0–9, a–z и A–Z (других диапазонов не будет). В этом случае будет искаться один любой символ из указанного диапазона (диапазонов). Если же первый символ в квадратных скобках – “!”, то, наоборот, искаться будет любой символ, из не перечисленных после восклицательного знака в квадратных скобках (например, [!.a-z,] означает один любой символ кроме точки, запятой, и строчных латинских букв). Если же искать надо один из специальных символов !, ?, [, ], (, ), –, \ то, как в квадратных скобках, так и без скобок перед таким символом ставится \.

Еще одно замечательное свойство строки поиска – выражения. Выражением считается часть строки поиска, взятая в круглые скобки. Пар скобок может быть до 9, но вложенность не допускается. В строке замены выражения представляются в виде \n, где n – порядковый номер выражения в шаблоне поиска (от 1 до 9). Например, по шаблону поиска (k)(?)t и шаблону замены t\2\1 произойдут например, следующие замены:
kot -> tok
kit -> tik

Таким образом, в строке замены существует только один специальный символ – \ , после которого обязательно должна идти цифра. Причем, например, цифра 5 может идти только если в строке поиска было не менее пяти выражений в скобках. При этом символы !, ?, [, ], (, ), – в строке замены указываются без предшествующего символа , а символ \ используется только перед цифрой и обозначает номер выражения. В качестве символа, который должен попасть в конечный текст, символ \ в строке замены не может быть использован.

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

Требуется по данному образцу поиска и образцу замены, произвести все замены в заданном тексте.

Входные данные
В первой строке входных данных расположен текст, в котором требуется произвести все необходимые замены. Длина текста не превышает 100 символов. Во второй строке записан шаблон для поиска. Шаблон является корректным: каждой открывающей скобке соответствует закрывающая, восклицательный знак как спецсимвол употребляется только сразу за символом [ и т.д. В третьей строке расположен шаблон для замены. Выражения в шаблоне для замены также корректны. Длины шаблонов не превышают 100 символов. Коды всех символов, встречающихся как в тексте, так и в шаблонах находятся в диапазоне от 32 до 126. Символы перевода строки в сами шаблоны и в текст не входят.

Выходные данные
Выведите одну строку – текст после всех произведенных замен.

Петя нарисовал на клетчатой бумаге прямоугольник по линиям сетки. После этого он подсчитал количество узлов сетки, оказавшихся внутри (не на границе!) прямоугольника и количество единичных отрезков сетки внутри прямоугольника и сообщил эти два числа Васе. Напишите программу, которая поможет Васе определить длины сторон прямоугольника.

Входные данные
Вводятся два целых неотрицательных числа K и L – количество узлов и единичных отрезков сетки соответственно. Оба числа не превосходят 1000.

Выходные данные
Выведите два натуральных числа – длины сторон прямоугольника в любом порядке. Если ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует.

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k
 досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной.

Требуется выяснить, какое минимальное расстояние Тому необходимо пройти, чтобы покрасить забор.

Входные данные
Первая строка содержит количество досок в заборе n (1 ≤ n ≤ 10⁹) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50).
Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ l_i ≤ r_i ≤ n). Такое описание означает, что не покрашены l_i-я, (l_i+1)-я, …, (r_i–1)-я, r_i-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

Выходные данные
Выведите одно число — минимальное расстояние в футах, которое необходимо пройти Тому для выполнения своего ответственного задания.

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

Восстановите нарисованный Васей многоугольник.

Входные данные
В первой строке входных данных содержатся два натуральных числа: Y - количество строк и X - количество столбцов листа (3 <= Y <= 1000, 3 <= X <= 1000). В каждой из следующих Y строк задается по X целых неотрицательных чисел, не превосходящих 4. Ни одна из сторон многоугольника не проходит по границе листа бумаги.

Выходные данные
Выведите искомый многоугольник в следующем формате.

Выходные данные должны содержать Y строк по 2X-1 символов в каждой (по одному символу на клетку и линию между клетками).

В первой строке выведите вертикальные отрезки в верхнем ряду клеток, обозначая их символом | (вертикальная черта - символ с кодом 124) и горизонтальные отрезки, отделяющие первый ряд клеток от следующего, обозначая их символом _ (подчеркивание). Если соответствующий отрезок в данном многоугольнике отсутствует, выведите вместо него символ . (точка). Во второй строке выведите в том же формате вертикальные отрезки во втором ряду и горизонтальные отрезки, отделяющие второй ряд от третьего. И т.д. В каждой строке на нечетных местах могут стоять только символы точка или подчеркивание, на четных местах - символы точка или вертикальная черта.

Гарантируется, что хотя бы одно решение существует. Если решений несколько, выведите любое из них.

Недавно Петя научился считать. Он тут же заметил, что число 2 обладает замечательным свойством - 2 + 2 = 2 × 2. Его старший брат Ваня тут же объяснил ему, что дело не в двойке.

"Дело в том, что последовательность 2, 2 - волшебная," - сказал Пете Ваня. - "Волшебная последовательность - это такая последовательность натуральных чисел, что сумма ее членов равна их произведению. Например последовательность 1, 2, 3 - тоже волшебная."

Петя тут же сложил 1, 2 и 3, потом перемножил их и обрадовался.

Теперь Петя хочет найти более длинные волшебные последовательности. Помогите ему!

Входные данные
В первой строке входных данных содержится целое число N (2 <= N <= 100).

Выходные данные
Выведите любую волшебную последовательность длины N. Разделяйте числа пробелами. Члены последовательности не должны превышать 10⁹. Если такой волшебной последовательности длины N не существует, выведите единственное число - "-1".

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

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

Теперь Андрюша хочет положить эти две фигуры на стол так, чтобы получилась клетка для хомячка. Фигуры должны быть положены таким образом, чтобы каждый кубик касался стола гранью. Стороны нижних граней кубиков должны быть параллельны сторонам стола. Любые два кубика, принадлежащие различным фигурам, должны либо не касаться друг друга, либо иметь общую грань, либо иметь общее ребро. Фигуры разрешается поворачивать и переворачивать.


Положив фигуры, Андрюша собирается выпустить хомячка на стол. Чтобы он не упал со стола, у него не должно быть возможности добраться от точки, в которую Андрюша его выпустит, до края стола. Хомячок не может перелезать через кубики, и, в частности, не может пролезть между двумя кубиками, имеющими общее ребро. Стол существенно больше каждой из фигур.

Андрюша хочет, чтобы площадь, по которой может бегать хомячок, была как можно больше. Помогите ему выяснить, какая максимальная площадь может быть у территории, до которой сможет добраться хомячок. Площадь грани кубика будем считать равной единице.

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

Входные данные
В первой строке вводятся два числа: h₁ и w₁ (1 <= h₁, w₁ <= 10). Следующие h₁
строк содержат по w₁ символов и описывают первую фигуру, вид сверху. Каждый из этих символов - либо "*" (звездочка), либо "." (точка), звездочка обозначает кубик, а точка – пустое место.

Далее в отдельной строке вводятся два числа: h₂ и w₂  (1 <= h₂,  w₂ <= 10). Следующие h₂ строк содержат по w₂ символов и описывают вторую фигуру в формате, аналогичном формату первой. Каждая из фигур связна и содержит хотя бы один кубик.

Выходные данные
Выведите одно число – максимальную площадь, которая может быть доступна хомячку. Если сделать клетку для хомячка невозможно, выведите 0.

Сколько существует клеток на доске размером K * K таких, что шахматный конь, стоящий на этой клетке, бьет ровно N полей?

Входные данные
Вводятся натуральные числа K и N (1 ≤ K ≤ 100, 2 ≤ N ≤ 8).

Выходные данные
Выведите количество клеток, с которых конь бьет ровно N
полей.

Комментарий
на доске 8*8 конь бьет ровно два поля только с угловых клеток, их 4.

Для идентификации ресурсов в сети Internet используются URL (Uniform Resource Locator). URL состоит из нескольких элементов: протокол, хост, порт, путь, файл и секция. Некоторые элементы URL могут быть опущены. Рассмотрим упрощенный формат URL:

[протокол://]хост[:порт][путь/[файл[#секция]]]
Заключенные в квадратные скобки элементы могут быть опущены, т.е. например, можно не указать протокол или секцию. Но, например, если указан файл, то обязательно должен быть указан путь. Регистр букв в элементах URL не важен.

Рассмотрим кратко все элементы URL:

*Протокол - это способ доступа к файлу, URL с разными протоколами и одинаковыми остальными элементами могут указывать на различные ресурсы.
*Хост и порт - это имя некоторого сервера в сети и способ доступа к нему (порт - натуральное число, не превосходящее 65535).
*Путь представляет собой путь к файлу, содержащему запрашиваемый ресурс, от некоторого каталога на сервере, который называется корневым. При этом для разделения имен каталогов используется символ "/". Путь, если он не пуст, всегда начинается с символа "/". Специальное обозначение '.' соответствует самому каталогу, '..' - родительскому каталогу.
*Файл - это файл, содержащий запрашиваемый ресурс.
Наконец, файл может быть разбит на секции каким либо способом и можно указать, к какой именно секции вы хотите обратиться.

Различные символы в URL могут быть заменены своими шестнадцатеричными ASCII кодами с помощью символа %, например a = %41, Z = %5A. В коде всегда используется ровно две шестнадцатеричные цифры.

Некоторые символы могут встречаться в элементах URL только как шестнадцатеричные коды - все символы, кроме букв латинского алфавита, цифр и символов "." и "-", а некоторые не могут встречаться вообще: "\", "#", "*", "@", "%", "?", ":", ",", а также символы с ASCII-кодом меньше %20. Символ "/" может встречаться в элементах URL только в пути для разделения входящих в него каталогов. Имя файла не может состоять только из точек.

Рассмотрим примеры URL:

http://neerc.ifmo.ru/school
ftp://somewhere.net:1234/pub/files/coolgame.zip
nobody.nowhere.net/some%20dir/some%20file#some%20info


Ваша цель в этой задаче - помочь разработчикам web-сервера. Для web-сервера отсутствующие части URL имеют следующие значения по умолчанию:

Протокол	http
Порт	80
Путь	пустая строка
Файл	index.html
Секция	пустая строка

Различные как строки URL могут указывать на один и тот же ресурс, например следующие три URL:

neerc.ifmo.ru
http://neerc.ifmo.ru:80/index.html#
Http://NEERC.IFMO.Ru/Dir/../././

Для разграничения доступа к ресурсам необходимо уметь определять, указывают ли два различных URL на один и тот же ресурс. Помогите разработчикам написать соответствующую проверку.

Входные данные
Входные данные состоят из двух строк, каждая из них содержит URL. Оба URL удовлетворяют формату, приведенному в условии этой задачи. Длина каждого URL не превосходит 200 символов. Гарантируется, что ни один из промежуточных каталогов на пути к ресурсу не лежит выше корневого каталога (т.е. не может встретиться, например, URL http://somewhere.com/../dir/index.html) а также, что имена всех каталогов состоят по крайней мере из одного символа (два символа "/" не могут идти подряд в любом месте, кроме как непосредственно после двоеточия после имени протокола).

Выходные данные
Выведите YES, если оба URL, приведенные во входных данных, указывают на один и тот же ресурс, и NO в противном случае.

Государство Флатландия представляет собой прямоугольник размером M × N, состоящий из единичных квадратиков. Флатландия разделена на K провинций (2 <= K <= 100). Каждая провинция представляет собой связное множество квадратиков, т.е. из каждой точки провинции можно дойти до любой другой ее точки, при этом разрешается переходить с квадратика на квадратик, только если они имеют общую сторону (общей вершины недостаточно). Во Флатландии нет точки, которая граничила бы более чем с тремя провинциями (т.е. четыре квадратика, имеющие общую вершину, не могут принадлежать четырем разным провинциям).

Каждая провинция имеет свой символ. Столица Флатландии находится в провинции, которой принадлежит символ A (заглавная латинская буква A). Провинция называется пограничной, если она содержит граничные квадратики. Провинция, в которой находится столица Флатландии, не является пограничной.

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

Чтобы окружить провинцию, требуется захватить все провинции, с которыми она граничит. Две провинции граничат, если существует два квадратика, имеющие общую сторону, один из которых принадлежит первой из них, а другой - второй. Чтобы захватить провинцию, надо чтобы выполнялось одно из двух условий: либо она пограничная, либо граничит с какой-либо уже захваченной провинцией.

Чтобы сберечь силы своей армии, король Ректилании хочет установить блокаду столичной провинции, захватив как можно меньше провинций. Помогите ему выяснить, сколько провинций требуется захватить. Захватывать столичную провинцию нельзя, поскольку для этого сил армии Ректилании пока недостаточно.

Входные данные
В первой строке вводятся числа M и N (3 <= M, N <= 200). Следующие M строк содержат N символов каждая и задают карту Флатландии. Символ, находящийся в i + 1-й строке входных данных на j-м месте, представляет собой символ провинции, которой принадлежит квадратик (i, j). Все символы имеют ASCII-код больше 32 (пробела).

Выходные данные
Выведите единственное число - количество провинций, которые требуется захватить. Если установить блокаду невозможно, выведите "-1".

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до N (то есть выписывает все числа от 1 до N в некотором порядке) и расставляет на столе в ряд N предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте, на место с номером a_i.

Обозначим предметы числами от 1 до N. Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, ..., N). К примеру, если N = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку <2, 5, 4, 3, 1>. Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте на место с номером a_i. Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.

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

Входные данные
Вводится единственное целое число N - количество предметов (1 <= N <= 100).

Выходные данные
Выведите перестановку чисел от 1 до N такую, что количество действий, которое придется сделать Пете, максимально. Если таких перестановок несколько, можно вывести любую.