Задача J. Jade portal

Автор:Артем Завгороднев   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

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

Вы попали в странный мир, и у вас на руках оказалось n рун со странным знаками на них. Вы видите перед собой неработающий нефритовый портал, в котором есть k ячеек.

Немножко поигравшись, вы заметили, что у рун есть своя энергия, и если попытаться засунуть руну в ячейку, то появится вспышка разных цветов:

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

Чтобы в ячейках не было рун разной энергии, когда вы видите синюю или красную вспышку, вы кладете только что добавленную руну обратно (К себе в карман или в ее прежнюю ячейку, в зависимости от того, где она была до этого). Неправильное расставление и возврат руны назад считаются за одну попытку.

Вам необходимо все руны раскидать по ячейкам. Гарантируется, что такое расположение рун существует. Времени у вас мало, поэтому вы можете сделать не более 15 * n попыток расставления.

Формат входных данных

При запуске решения на вход в первой строке подаются два целых числа k и n - количество ячеек в портале и количество рун.

Формат выходных данных

Вы можете делать запросы посредством вывода «? i j», где i,j - номер руны и номер ячейки, в которую вы собираетесь положить эту руну соответственно.

Ответом будет выведена одна из строчек «White», «Blue», «Green» или «Red» в зависимости от рун в ячейке.

Вы можете сделать не более 15 * n запросов. Вывод ответа не считается за запрос.

Вы можете вывести ответ, выведя «!», если считаете, что расположили все руны по их энергии.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Язык C++ Pascal Java Python
Сброс буфера cout.flush() flush(output) System.out.flush() stdout.flush()

Ограничения

1 ≤ k < n ≤ 1000

Пояснение к примеру

Энергия рун в данном примере была следующая: a3 a2 a2 a1, где a3 > a2 > a1

Примеры тестов

Стандартный вход Стандартный выход
1
3 4

White

Blue

White

Blue

Green

Blue

White
? 1 1

? 2 1

? 2 2

? 3 1

? 3 2

? 4 2

? 4 3

!

0.088s 0.018s 13