Задача J. Jade portal ≡

Условие

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

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

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

• Белая, если в этой ячейке нет других рун.
• Синяя, если руна, которую вы пытаетесь положить имеет меньшую энергию, чем руны, которые уже лежат в этой ячейке.
• Зеленая, если руна, которую вы пытаетесь положить имеет такую же энергию, как руны, которые уже лежат в этой ячейке.
• Красная, если руна, которую вы пытаетесь положить имеет большую энергию, чем руны, которые уже лежат в этой ячейке.

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ k < n ≤ 1000

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

Энергия рун в данном примере была следующая: a₃ a₂ a₂ a₁, где a₃ > a₂ > a₁

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

3 4

White

Blue

White

Blue

Green

Blue

White

? 1 1

? 2 1

? 2 2

? 3 1

? 3 2

? 4 2

? 4 3

!