Это интерактивная задача.
Рассмотрим следующую игру для двух игроков:
- Изначально на доску выписывается массив целых чисел $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$.
- Игра состоит из раундов. На каждом раунде происходит следующее:
- Первый игрок выбирает любое $$$i$$$, такое, что $$$a_i \gt 0$$$. Если такого $$$i$$$ не существует, первый игрок проигрывает (второй игрок выигрывает) и игра заканчивается.
- Второй игрок выбирает любое $$$j \neq i$$$, такое, что $$$a_j \gt 0$$$. Если такого $$$j$$$ не существует, второй игрок проигрывает (первый игрок выигрывает) и игра заканчивается.
- Вычисляется $$$d = \min(a_i, a_j)$$$. Значения $$$a_i$$$ и $$$a_j$$$ одновременно уменьшаются на $$$d$$$, после чего начинается следующий раунд.
Можно показать, что игра всегда заканчивается после конечного числа раундов.
Выберите, за кого вы хотите сыграть (за первого игрока или за второго) в эту игру, и выиграйте за него.
Протокол взаимодействия
Взаимодействие начинается после считывания $$$n$$$ и массива $$$a$$$.
Вы должны начать взаимодействие с вывода одной строки «First» или «Second», обозначающей игрока, за которого вы будете играть.
На каждом раунде происходит следующее:
- Если вы выбрали первого игрока, то вы должны вывести одно целое число $$$i$$$ ($$$1 \le i \le n$$$) в отдельной строке. После этого вы должны считать одно целое число $$$j$$$ ($$$-1 \le j \le n$$$), выведенное в отдельной строке.
Если $$$j = -1$$$, то это значит, что вы сделали некорректный ход. В таком случае вы должны немедленно завершить вашу программу.
Если $$$j = 0$$$, то это значит, что второй игрок не может сделать корректный ход, и, соответственно, вы выигрываете игру. В этом случае вы также должны завершить вашу программу.
Иначе $$$j$$$ равняется индексу, выбранному вторым игроком, и вы должны перейти к следующему раунду.
- Если вы выбрали второго игрока, то вы должны считать одно целое число $$$i$$$ ($$$-1 \le i \le n$$$), выведенное в отдельной строке.
Если $$$i = -1$$$, то это значит, что вы сделали некорректный ход на предыдущем раунде. В этом случае вы должны немедленно завершить вашу программу.
Если $$$i = 0$$$, то это значит, что первый игрок не может сделать корректный ход и вы выигрываете игру. В этом случае вы также должны завершить вашу программу.
Иначе $$$i$$$ равняется индексу, выбранному первым игроком. В таком случае вы должны вывести одно целое число $$$j$$$ ($$$1 \le j \le n$$$) в отдельной строке и перейти к следующему раунду.
После вывода $$$i$$$ или $$$j$$$ не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
В этой задаче отключены взломы.
Примеры
Выходные данные
First
1
2
4
Выходные данные
Second
4
4
3
1
3
Примечание
В первом примере $$$n = 4$$$ и массив $$$a$$$ равен $$$[\, 10, 4, 6, 3 \,]$$$. Ход игры будет следующим:
- После считывания массива $$$a$$$ программа участника выбирает первого игрока и выводит «First».
- Первый раунд: первый игрок выбирает $$$i = 1$$$, второй игрок выбирает $$$j = 3$$$. Считается $$$d = \min(a_1, a_3) = \min(10, 6) = 6$$$. Элементы $$$a_1$$$ и $$$a_3$$$ уменьшаются на $$$6$$$. Массив $$$a$$$ становится равен $$$[\, 4, 4, 0, 3 \,]$$$.
- Второй раунд: первый игрок выбирает $$$i = 2$$$, второй игрок выбирает $$$j = 1$$$. Считается $$$d = \min(a_2, a_1) = \min(4, 4) = 4$$$. Элементы $$$a_2$$$ и $$$a_1$$$ уменюшаются на $$$4$$$. Массив $$$a$$$ становится равен $$$[\, 0, 0, 0, 3 \,]$$$.
- Третий раунд: первый игрок выбирает $$$i = 4$$$. Не существует $$$j \neq 4$$$, такого, что $$$a_j > 0$$$, поэтому второй игрок не может сделать ход и первый игрок выигрывает. Интерактор выводит $$$j = 0$$$, после считывания которого программа участника завершается.
Во втором примере $$$n = 6$$$ и массив $$$a$$$ равен $$$[\, 4, 5, 5, 11, 3, 2 \,]$$$. Ход игры будет следующим:
- Программа участника выбирает второго игрока и выводит «Second».
- Первый раунд: $$$i = 2$$$, $$$j = 4$$$, $$$a = [\, 4, 0, 5, 6, 3, 2 \,]$$$.
- Второй раунд: $$$i = 5$$$, $$$j = 4$$$, $$$a = [\, 4, 0, 5, 3, 0, 2 \,]$$$.
- Третий раунд: $$$i = 4$$$, $$$j = 3$$$, $$$a = [\, 4, 0, 2, 0, 0, 2 \,]$$$.
- Четвертый раунд: $$$i = 6$$$, $$$j = 1$$$, $$$a = [\, 2, 0, 2, 0, 0, 0 \,]$$$.
- Пятый раунд: $$$i = 1$$$, $$$j = 3$$$, $$$a = [\, 0, 0, 0, 0, 0, 0 \,]$$$.
- Шестой раунд: первый игрок не может сделать ход и второй игрок выигрывает. Интерактор выводит $$$i = 0$$$, после считывания которого программа участника завершается.
Обратите внимание, что лишние переводы строки в примерах приведены только для удобства и в действительности вам не нужно их выводить. Программа жюри также не будет выводить лишних переводов строки.