Граф называется деревом если он связен и не содержит циклов. Предположим, у дерева выбран корень. Тогда дерево называется полным \(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\).