«Заяц» и контролер играют в следующую игру.

Электричка представляет собой n вагонов, которые нумеруются натуральными числами от 1 до n в порядке от головы до хвоста. «Заяц» и контролер изначально находятся в некоторых двух различных вагонах. Электричка каждую минуту может быть в одном из двух состояний — в движении или на остановке. Каждую минуту игроки делают ходы.

Ход контролера заключается в следующем. Контролер имеет направление движения — к голове электрички или к ее хвосту. За свой ход контролер перемещается в соседний вагон в соответствии со своим направлением движения. Если по окончании своего хода контролер заходит в 1-ый или n-ый вагон, то он меняет свое направление движения на противоположное. Другими словами — контролер циклически ходит от головы электрички до хвоста и обратно в течение всего времени игры, на каждом ходу сдвигаясь на один вагон. Заметим, что у контролера есть всегда есть ровно один допустимый ход.

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

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

Если в какой-то момент времени «заяц» и контролер оказываются в одном вагоне, то выигрывает контролер: он заставляет «зайца» выплатить штраф. Если через некоторое время «заяц» доезжает до конечной остановки — выигрывает «заяц»: своим ходом он просто выходит из электрички и более в нее не возвращается.

В любой момент времени игроки знают положения друг друга. Игроки играют оптимально. В частности, если выигрывает контролер, то «заяц» играет так, чтобы проиграть как можно позже. Поскольку для контролера возможные ходы определены однозначно, то считается, что он играет оптимально всегда. Определите победителя.