Это интерактивная задача.
Рассмотрим следующую игру для двух игроков:
- Изначально на доску выписывается массив целых чисел \(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;
- смотрите документацию для других языков.
Взломы
В этой задаче отключены взломы.
Примечание
В первом примере \(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\), после считывания которого программа участника завершается.
Обратите внимание, что лишние переводы строки в примерах приведены только для удобства и в действительности вам не нужно их выводить. Программа жюри также не будет выводить лишних переводов строки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
10 4 6 3
3
1
0
|
First
1
2
4
|
|
2
|
6
4 5 5 11 3 2
2
5
4
6
1
0
|
Second
4
4
3
1
3
|