Граф называется деревом если он связен и не содержит циклов. Предположим, у дерева выбран корень. Тогда дерево называется полным $$$k$$$-ичным если каждая вершина или является листом (не имеет сыновей) или имеет ровно $$$k$$$ сыновей. Также все листья полного $$$k$$$-ичного дерева должны иметь одинаковую глубину.

Например, на картинке ниже изображено полное двоичное дерево из $$$15$$$ вершин.

Выбрано полное $$$k$$$-ичное дерево из $$$n$$$ вершин. Вершины помечены различными целыми числами от $$$1$$$ до $$$n$$$, однако вы не знаете каким именно образом помечены вершины. Тем не менее, вы хотите выяснить пометку у корня дерева.

Вы можете выполнить не более $$$60 \cdot n$$$ запросов следующего вида:

• «? $$$a$$$ $$$b$$$ $$$c$$$», запрос возвращает «Yes» если вершина с пометкой $$$b$$$ лежит на пути от $$$a$$$ до $$$c$$$ и «No» иначе.

Вершины $$$a$$$ и $$$c$$$ считаются лежащими на пути от $$$a$$$ до $$$c$$$.

Когда вы будете готовы сообщить пометку корня дерева выведите

• "! $$$s$$$", где $$$s$$$ является пометкой корня.

Разрешается вывести номер корня ровно один раз и эта операция не учитывается относительно ограничения на $$$60 \cdot n$$$ запросов.

Первая строка стандартного потока ввода содержит два целых числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k < n$$$) — количество вершин в дереве и значение параметра $$$k$$$.

Гарантируется, что $$$n$$$ таково, что дерево является полным $$$k$$$-ичным.

Вы можете задать не более $$$60 \cdot n$$$ запросов. Чтобы выполнить запрос выведите строку вида «? $$$a$$$ $$$b$$$ $$$c$$$», где $$$1 \le a, b, c \le n$$$. После этого считайте одну строку содержащую или «Yes» или «No», в зависимости от результата запроса.

Дерево зафиксировано для каждого теста и не зависит от запросов вашего решения.

Когда вы готовы вывести ответ, выведите строку вида «! $$$s$$$», где $$$s$$$ является пометкой корня, и завершите вашу программу после этого.

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

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

В случае, если ваша программа сделает более $$$60 \cdot n$$$ запросов, но в остальном будет следовать протоколу взаимодействия и корректно завершится, то вы получите вердикт «Неправильный Ответ».

Взломы

Чтобы взломать решение используйте следующий формат теста:

Первая строка должна содержать целые числа $$$n$$$ и $$$k$$$ ($$$3 \le n \le 1500$$$, $$$2 \le k \le 1500$$$) — количество вершин и параметр $$$k$$$ дерева.

Разумеется, значение $$$n$$$ должно соответствовать размеру полного $$$k$$$-ичного дерева какой-то глубины.

Вторая строка должна содержать $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — пометки вершин дерева при их обходе в естественном порядке, все пометки должны быть различными.

Назовём следующий порядок вершин естественным: сначала записан корень дерева, затем записаны все вершины на расстоянии одного ребра в порядке слева направо, затем записаны все вершины на расстоянии двух рёбер в порядке слева направо, и так далее до наибольшей глубины.

В частности, ответом на взлом является $$$a_1$$$.