Ефим и Серафим целый день играли в ним. Ефим всегда выигрывал, поэтому Серафиму надоело играть с ним и он решил изменить игру.

Есть одна кучка из n камней.

Игроки ходят по очереди. Проигрывает тот, кто возьмёт последний камень.

На первом ходу игрок может взять любое количество камней от 1 до n.

На каждом последующем ходу игрок ограничен в своём ходе относительно P — сколько камней было взято другим игроком на предыдущем ходу. На текущем ходу игрок может взять количество камней S такое, что оно равно P, либо такое, что чётности P и S различаются. Например, если на предыдущем ходу было взято 5 камней, то сейчас можно взять либо также 5, либо любое чётное положительное количество.

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

Два игрока играют оптимально. То есть ходят, стараясь привести игру к своему выигрышу, а если это невозможно, то к ничье.

Определите для заданного n кто выиграет в игре.