Сегодня Маша принимает гостей. Включая Машу, в празднике принимает участие \(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\). Традиционно на ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.

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

Джон — фанат сериала «Во все престолы». Совсем скоро выходит новый сезон, и Джон хочет его посмотреть.

Серии будут выходить по одной в день. Джону не хочется скачивать их каждый раз вручную, поэтому он собирается написать программу, которая будет делать это за него. Каждая серия — это отдельный файл, размер файла, содержащего \(i\)-ю серию, равен \(s_i\) байт.

Программа Джона будет действовать следующим образом. Она один за другим будет отправлять на сервер запросы, где \(j\)-й запрос представляет собой «загрузить очередные \(x_j\) байт». В ответ на такой запрос сервер возвращает пакет данных, содержащий очередные \(x_j\) байт файла, а также заголовок, содержащий \(k\) байт различной служебной информации. Таким образом, размер пакета равен \(x_j + k\) байт, при этом значение \(k\) одно и то же для всех запросов.

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

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

Из-за утечки информации от создателей сериала Джону известен размер каждой серии. Помогите ему узнать, какой минимальный суммарный размер пакетов придётся загрузить, чтобы скачать все серии.