Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 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 раз.

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

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

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

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

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

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

Петя склеил из \(N^3\) единичных кубиков большой куб размером \(N\) × \(N\) × \(N\). Устав от этой сложной работы, он отправился спать, а утром, проснувшись, с ужасом обнаружил, что его младший брат Ваня \(K\) раз проткнул куб спицей.

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

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

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

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

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

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

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