Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник \(n \times m\), который полностью состоит из маленьких шоколадных долек — прямоугольников \(2 \times 1\).

Помогите Пете поделиться шоколадкой с Машей.

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

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

Будем считать, что Луна на снимке выглядит как круг с центром в точке изображения \(C\) и целым неотрицательным радиусом r, то есть как множество белых точек, расстояние от центров которых до точки \(C\) не больше \(r\). Луна полностью поместилась на снимке.

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

Юная любительница ювелирных изделий Октябрина к празднику 4-го ноября хочет подарить своей лучшей подруге Тракторине ожерелье из \(n\) черных и розовых жемчужин.

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

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

Недавно руководством одной известной автомобильной телепередачи «Верхняя шестерня» было решено провести обзор автомобилей на солнечных батареях. Для этого были выбраны две модели.

К сожалению, современные технологии еще далеки от совершенства, поэтому автомобили не могут ехать непрерывно. Руководство по эксплуатации первого автомобиля гласит, что при передвижении на большие дистанции нужно действовать следующим образом: в течение \(t_1\) часов ехать со скоростью \(v_1\) километров в час, после чего такое же время заряжать батареи. Стратегия по оптимальному использованию второго автомобиля аналогична, но числа \(t_2\) и \(v_2\) для него могут отличаться.

Для демонстрации работы автомобилей было решено устроить соревнование — заезд по прямой трассе длиной \(X\) километров, придерживаясь стратегии из руководства.

Вам поручено предсказать результат этого заезда.

Робот-марсоход «ТцТцПетя» двигается по поверхности Марса как ему вздумается, отправляя на Землю информацию о своих передвижениях.

«ТцТцПетя» пользуется следующей системой координат: начало координат совпадает с его начальным положением, ось \(OY\) направлена в сторону, в которую он направлен в начальный момент времени (при высадке на Марс).

Передвигается «ТцТцПетя» следующим образом: после высадки на Марс он проезжает вперед какое-то целое число сантиметров, от \(1\) до \(10^6;\) затем поворачивает на \(90\) градусов либо налево, либо направо; после чего снова проезжает вперед от \(1 \ до \ 10^6\) сантиметров; и снова поворачивает на \(90\) градусов либо налево, либо направо; и так далее. Наконец, проехав последний отрезок (также длиной от \(1\) до \(10^6\) сантиметров), он останавливается и начинает передавать на Землю описание своего маршрута.

В итоге Центр Управления получил от «ТцТцПети» следующее сообщение: «Я сделал n передвижений. Сообщаю \(n \ − \ 1\) поворот, который я совершил: последовательность поворотов. В итоге я оказался в точке с координатами \((x, \ y).\) Мне тут нравится. Конец связи.»

И тут-то создатели «ТцТцПети» поняли, что забыли запрограммировать его, чтобы он сообщал длины своих передвижений!

Теперь их интересует хоть какой-нибудь вариант пути «ТцТцПети», который удовлетворяет полученным от него данным. Помогите им.