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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером \(1\times1\times L\), на одной из сторон которого есть место для рекламы — пространство размера \(1\times L\), в которое можно вписать ровно \(L\) букв латинского алфавита.

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

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

После того, как некоторое число \(K\) блоков, каждый из которых имеет длину \(L\), поставили друг на друга, получилась прямоугольная таблица размером \(K\times L\), в каждой клетке которой находится буква латинского алфавита. Каждый рекламный блок соответствует строке этой таблицы. Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого. При этом в каждом столбце буквы выписываются сверху вниз. В случае, изображённом на рисунке, в результате этого процесса получилась бы строка «TOEIIZENITKN». Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока «TOEIIZENITKN».

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

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

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

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

У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из \(n\) клеток. Каким будет максимальный объём коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нём. Поликарп может использовать для оклеивания коробки не все клетки.

Напишите программу, которая по заданному количеству клеток \(n\) находит размеры коробки максимального возможного объема.

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.

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

• Пустая строка является корректной XML-строкой.
• A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
• Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:

<a></a>

<a><ab></ab><c></c></a>

<a></a><a></a><a></a>

являются корректными XML-строками, а такие строки как:

<a></b>

<a><b>

<a><b></a></b>

не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

У Пети имеется игровое поле размером \(3\times3\), заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.