C. Выбери героев
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Всего есть $$$2$$$ команды по $$$n$$$ игроков и $$$2n$$$ героев, которых нужно распределить по игрокам. Команды по очереди выбирают героев: сначала первая команда выбирает одного героя в свою команду, затем вторая команда выбирает одного героя себе и так далее. Обратите внимание, что после того, как герой выбран, его больше не может выбрать ни та, ни другая команда.

Друзья оценивают силу $$$i$$$-го героя как $$$p_i$$$. Каждая команда хочет максимизировать суммарную силу своих героев. Однако, есть одно исключение: есть $$$m$$$ пар героев, которые особенно сильны друг против друга, поэтому когда одна команда выбирает героя из пары, другая команда на своем ходу обязана выбрать другого героя из пары. Каждый герой входит максимум в одну такою пару.

Это — интерактивная задача. Вам нужно написать программу, которая будет оптимально выбирать героев в одну команду, в то время как программа жюри будет играть за другую команду. Обратите внимание, что программа жюри может играть не оптимально, в таком случае вам необходимо использовать шанс и все равно максимизировать суммарную силу своей команды. Формально, если в какой-то момент у вас есть возможность набрать суммарную силу героев в $$$q$$$ или больше, независимо от дальнейших ходов программы жюри, вы должны набрать $$$q$$$ или больше для того, чтобы пройти тест.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$0 \le m \le n$$$) — количество игроков в одной команде и количество специальных пар героев.

Следующая строка содержит $$$2n$$$ целых чисел $$$p_1, p_2, \ldots, p_{2n}$$$ ($$$1 \le p_i \le 10^3$$$) — силы героев.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le 2n$$$, $$$a \ne b$$$) — пару героев, которые особенно сильны друг против друга. Гарантируется, что каждый герое встречается не более одного раза в этом списке.

Следующая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2$$$) — номер команды, за которую вы должны играть. Если $$$t = 1$$$, то первый ход ваш, иначе ваш ход — второй.

Взломы

Чтобы совершить взлом, используйте формат, описанный выше, дополненный одной строкой. В этой строке выведите $$$2n$$$ различных целых числа от $$$1$$$ до $$$2n$$$ — приоритетный порядок для команды жюри. Команда жюри будет выбирать на каждом ходу подходящего героя, стоящего в этом списке раньше остальных. Здесь подходящий герой означает, что он еще никем не выбран, а также не противоречит правилу о специальных парах героев.

Протокол взаимодействия

Когда очередь ходить ваша, выведите одно целое число $$$x$$$ ($$$1 \le x \le 2n$$$) — индекс героя, которого вы выбираете. Обратите внимание, вы не можете выбрать героя, которого ранее выбрали вы либо другой игрок, и вы должны следовать правилу о специальных парах героев.

Когда очередь ходить вашему сопернику, считайте одно целое число $$$x$$$ ($$$1 \le x \le 2n$$$) — индекс героя, выбранного другой командой. Гарантируется, что выбранный герой не будет выбран ранее; гарантируется, что соперник будет следовать правилу о специальных парах героев.

После последнего хода вы должны завершиться, не выводя ничего.

После вывода хода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Ход жюри $$$-1$$$ означает, что ваша программа сделала некорректный ход. Ваша программа должна немедленно завершиться после прочтения ответа $$$-1$$$, вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

Примеры
Входные данные
3 1
1 2 3 4 5 6
2 6
1

2

4

1
Выходные данные




6

5

3
Входные данные
3 1
1 2 3 4 5 6
1 5
2
6

1

3
Выходные данные





5

4

2
Примечание

В первом примере первый ход ваш. В примере вы выбираете $$$6$$$, другая команда обязана выбрать $$$2$$$. Вы выбираете $$$5$$$, другая команда выбирает $$$4$$$. Наконец, вы выбираете $$$3$$$, а другая команда выбирает $$$1$$$.

Во втором примере вы ходите вторыми. Соперник выбирает $$$6$$$, вы выбираете $$$5$$$, заставляя соперника выбрать $$$1$$$. Затем вы выбираете $$$4$$$, другая команда выбирает $$$3$$$ и вы выбираете $$$2$$$.