Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу
один или
четыре камня либо увеличить количество камней в куче в
два раза. Например, имея кучу из 12 камней, за один ход можно получить кучу из 13, 16 или 24 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 35. Если при этом в куче оказалось нечетное количество камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем считается его противник, при этом считается, что противник сделал свой ход.
В начальный момент в куче было S камней; 1 ≤ S ≤ 34.
Вопрос 1
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Вопрос 2
Для описанной игры, найдите минимальное и максимальное значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3
Для описанной игры, найдите значение S, при котором одновременно выполняются два условия:
• у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите минимальное из них.
Формат ввода ответов
На каждое задание ответы пишите с новой строки. Если вы не знаете ответ на какое-либо задание, напишите в ответе любое число.
Например, если ответ на вопрос 1 - 1, на вопрос 2 - 2 и 3, на вопрос 3 - 4, то ответы надо записать так:
1
2 3
4