Это интерактивная задача.

Игорь хочет найти ключ к сердцу Ольги. Проблема в том, что он находится в корне бинарного дерева.

Есть полное бинарное дерево высотой $$$h$$$, состоящее из $$$n = 2^{h} - 1$$$ вершин. Вершинам были присвоены различные метки от $$$1$$$ до $$$n$$$. Однако Игорь знает только $$$h$$$ и не знает, какой метке соответствует какая вершина.

Чтобы найти ключ к сердцу Ольги, ему нужно найти метку, соответствующую корню, сделав запросы следующего типа не более $$$n+420$$$ раз:

• Игорь выберет три различные метки $$$u$$$, $$$v$$$ и $$$w$$$ ($$$1 \leq u,v,w \leq n$$$).
• В ответ Ольга (интерактор) скажет ему метку наименьшего общего предка вершин, помеченных $$$u$$$ и $$$v$$$, если бы корнем дерева была вершина, помеченная $$$w$$$.

Помогите Игорю найти метку корня дерева!

Примечание: интерактор не адаптивный: метки фиксируются перед выполнением каких-либо запросов.

Вы начинаете взаимодействие с чтения $$$h$$$.

Чтобы сделать запрос для меток $$$u, v, w$$$, в отдельной строке выведите «? u v w».

Числа в запросе должны удовлетворять $$$1 \le u, v, w \le n$$$. Дополнительно $$$u \ne v$$$, $$$u \ne w$$$ и $$$v \ne w$$$.

В ответ вы получите $$$1 \le x \le n$$$ — метку наименьшего общего предка $$$u$$$ и $$$v$$$, если бы корнем дерева была $$$w$$$.

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

Когда вы определите метку, присвоенную корню, выведите «! r», где $$$r$$$ — метка корня.

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

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

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

Формат взломов

Для взлома используйте следующий формат.

Первая строка должна содержать одно целое $$$h$$$ (высоту бинарного дерева).

В следующей строке выведите перестановку $$$p$$$ размером $$$n = 2^h - 1$$$. Она представляет собой бинарное дерево, в котором корень помечен $$$p_1$$$, а для $$$1 < i \le n$$$ непосредственным родителем $$$p_i$$$ является $$$p_{ \lfloor{\frac{i}{2}}\rfloor }$$$.