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

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

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

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

На листке записано в одну строку \(N\) (\(2 \leq N \leq 100\)) целых положительных чисел. Каждое число не превышает 200. Играют двое. За каждый ход можно зачеркивать крайнее число либо слева, либо справа. Зачеркнутое число добавляется к очкам игрока. \(N\) – четное. Игру начинает первый игрок. Необходимо вывести максимально возможную сумму очков для первого игрока при условии, что противник играет наилучшим образом..

Полицейский гонится за преступником по музею. В начале погони каждый из них находится в одной из \(n\) комнат здания, некоторые комнаты соединены дверями.

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

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

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

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

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

Петя с Андреем играют в интересную игру. Для этой игры им необходимо k шоколадок, каждая из которых имеет форму прямоугольника – i-ая из них имеет размер w_i на h_i долек.

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

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

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