Однажды Петя узнал очень важную последовательность из \(n\) чисел. Тщательно проанализировав ее, он обнаружил, что она является арифметической прогрессией. Чтобы не забыть он записал ее элементы на \(n\) карточках.

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

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

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

Напомним что последовательность \(a_1, a_2, \ldots, a_n\) называется арифметической прогрессией, если \(a_i = a_{i-1} + d\) для всех \(i\) от 2 до \(n\) и некоторого \(d\). Число \(d\) называется разностью арифметической прогрессии.

Робот Бендер решил открыть аттракцион «Кручу-Верчу» с целью своего обогащения. Аттракцион состоит в следующем: Бендер прячет шарик под одним из \(k\) одинаковых стаканчиков, расположенных на позициях от 1 до \(k\), затем \(n\) раз быстро меняет местами какие-то пары стаканчиков, после чего предлагает отгадать под каким из стаканчиков сейчас шарик.

Бендер — робот, поэтому действует он по определенной программе. Бендер строит последовательность целых чисел \(x_i\), при этом \(x_1 = c\), а \(x_i = a \cdot x_{i-1} + b\) для \(i > 1\).

На \(i\)-ом шаге Бендер меняет местами стаканчики на позициях с номерами \((x_i \bmod k) + 1\) и \(\left( (x_i + 1) \bmod k \right) + 1\).

В начале робот прячет шарик под стаканчик на позиции с номером \(r\). Бендер хочет, чтобы после \(n\) обменов шарик оказался под стаканчиком на позиции с номером \(l\).

Найдите такие \(a\), \(b\) и \(c\), чтобы стаканчик с шариком переместился с \(r\)-й позиции на \(l\)-ю.

На днях Алиса делала уборку в своей комнате и нашла дневник, который вела в начальной школе. Там она с удивлением обнаружила запись о том насколько ее поразило то, что \(2 + 2 = 2 \cdot 2\). Невероятно, умножение и сложение дают один и тот же результат!

Эта запись натолкнула Алису на следующую задачу: пусть целые заданы числа \(a\) и \(b\). Сколько различных значений в наборе чисел

Деление происходит без округления, результат деления может не быть целым числом. Если какое-либо выражение из этого набора некорректно, то Алиса его не рассматривает. Некорректными считаются деление на ноль и возведение нуля в неположительную степень.

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

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

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

Джон работает на огромной парковке. Парковка представляется собой прямоугольное поле \(n \times m\), разбитое на \(n \times m\) квадратных позиций размера \(1 \times 1\). Одну из угловых позиций занимает выезд с парковки.

Машин на парковке много и вывести машину не так уж просто. Единственное, что Джон может сделать — это переместить один из автомобилей на соседнюю позицию, если она свободна. Соседними считаются позиции, имеющие общую сторону. Однако задача усложняется наличием на парковке столбов. На позиции, где стоят столбы, нельзя поставить машину. Парковка вся занята машинами и столбами и единственное свободное место — выезд с парковки. Задача Джона — вывести с парковки один из автомобилей. Помогите ему узнать, какое минимальное число действий ему придется совершить.