Двое играют в следующую игру со строкой. Изначально у игроков есть некоторая строка s. Игроки делают ходы по очереди, а игрок, который не может сделать очередной ход, проигрывает.

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

Пример изначальной ситуации при s = «abacaba»

Ход игрока — это последовательность действий:

1. Игрок выбирает один из доступных листочков, на котором записана некоторая строка. Обозначим ее t. Заметим, что изначально доступен только один листочек.
2. Игрок выбирает в строке t = t₁t₂... t_|t| символ в позиции i (1 ≤ i ≤ |t|) такой, что для некоторого целого положительного l (0 < i - l; i + l ≤ |t|) выполняются равенства: t_i - 1 = t_i + 1, t_i - 2 = t_i + 2, ..., t_i - l = t_i + l.
3. Игрок вырезает ячейку с выбранным символом. В результате этой операции образуется три новых листочка, причем на первом будет записана строка t₁t₂... t_i - 1, на втором — строка, состоящая из одного символа t_i, на третьем — t_i + 1t_i + 2... t_|t|.

Пример выполнения действия (i = 4) со строкой s = «abacaba»

Ваша задача — определить, кто выиграет при оптимальной игре. Если при оптимальной игре выиграет тот, кто ходит первый, определите позицию символа, который выгодно вырезать первым ходом первому. Если таких позиций несколько, найдите минимально возможную.