Двое играют в следующую игру. Из кучки спичек за один ход игрок вытягивает либо 1, либо 2, либо 1000 спичек. Выигрывает тот, кто забирает последнюю спичку. Кто выигрывает при правильной игре?

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

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

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