Недавно на уроках ИЗО Казимиру рассказали о различных направлениях искусства. Больше всего его впечатлил супрематизм, и он решил нарисовать свою первую картину в этом стиле.

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

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

Помогите Казимиру определить, cможет ли он с помощью этих операций исправить свою картину и сделать ее достаточно простой.

Сегодня Маша принимает гостей. Включая Машу, в празднике принимает участие \(n\) человек, которые расселись по кругу за большим круглым столом.

Разумеется, Маша хочет пообщаться со многими гостями, но кричать через весь стол неудобно. Тогда она быстро придумала решение проблемы: иногда она просит соседа слева или справа от неё поменяться с ней местами. Гости, разумеется, любезно соглашаются на её просьбу.

Проводив гостей, Маша вспомнила, что забыла телефон на месте, на котором она сидела в конце мероприятия. Маша не помнит, на каком месте она сидела в конце, зато помнит, на каком месте она сидела в начале, а также помнит, что она ровно \(k\) раз менялась местами с одним из соседей. Теперь она хочет узнать количество мест, на которых она могла оказаться в конце вечера.

Каждое утро жители столицы Берляндии вынуждены стоять в ужасных пробках по дороге на работу. Особенно сильно эти пробки заметны на центральной площади столицы, которая представляет собой перекресток, да еще и нерегулируемый — берляндцы стремятся сохранить нетронутым исторический облик центра города.

Решив заняться исследованием ситуации, мэр столицы поручил изучить, как именно скапливаются пробки. Ведь на перекрестке запрещены повороты, таким образом, машины могут проезжать перекресток только прямо. Установив специальные датчики, специалисты выяснили, что каждое утро перекресток пытаются проехать n машин. К перекрестку подходят улицы с четырех сторон: если посмотреть на карту, то эти улицы идут в направлении вверх «U», влево «L», вниз «D» и вправо «R». На каждой из улиц в процессе проезда перекрестка может скапливаться очередь из машин.

Каждый водитель при подъезде к перекрестку действует следующим образом: \(i\)-й водитель подъезжает к перекрестку в начале \(t_i\)-й секунды, встает в конец очереди на этой улице и анализирует ситуацию.

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

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

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

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

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

Назовем циклической последовательностью ячеек такую последовательность ячеек \((x_1, y_1),(x_2, y_2)\dots(x_k, y_k)\), что каждая пара соседних в последовательности ячеек, а также первая и последняя ячейки в последовательности, не совпадают и имеют общую сторону. Таким образом, при перемещении конца волшебной палочки вдоль последовательности, каждый раз необходимо переместиться в соседнюю ячейку вверх, влево, вправо или вниз, а в конце — вернуться в начальную ячейку. При этом одна и та же ячейка может встречаться в последовательности несколько раз.

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

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

В Санкт-Петербурге открывают новую станцию метро, и для нее требуется произвести эскалатор. Эскалатор состоит из \(n\) ступенек, пронумерованных целыми числами от 1 до \(n\). Традиционно на ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.

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