I. Угадай дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Жюри задумало полное бинарное дерево с n = 2h - 1 вершинами. Его вершины пронумерованы целыми различными числами от 1 до n, однако вам неизвестно, какие вершины с какими соединены.

Вы можете спрашивать у программы жюри, чему равно расстояние между некоторыми двумя вершинами. Вы должны с помощью не более чем 2.5·h·n таких запросов восстановить структуру дерева.

Протокол взаимодействия

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

В самом начале вашей программе сообщается единственное число n (1 ≤ n ≤ 1023, n + 1 — степень двойки) — количество вершин в дереве.

После этого вы можете сделать не более 2.5·h·n запросов. Чтобы сделать запрос, выведите символ «?» и два целых числа от 1 до n — номера вершин x и y, расстояние между которыми вы хотите узнать. В ответ на такой запрос вам будет сообщено одно целое число — расстояние между вершинами x и y.

Как только вы узнаете полную структуру дерева, выведите символ «!», а затем n целых чисел pi, где pi — это предок вершины i, либо число 0, если вершина i является корнем дерева. После этого ваша программа должна завершиться.

Пример
Входные данные
<interactor's output>

? 1 2

<interactor's output>

? 2 3

<interactor's output>

! 2 0 2
Выходные данные
3

<solution's output>

1

<solution's output>

1

<solution's output>
Примечание

Обратите внимание, что каждое выведенное вами сообщение должно завершаться переводом строки. Также после вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри: например, это делают вызовы «fflush(stdout)» или «cout.flush()» в C++, «System.out.flush()» в Java, «Console.Out.Flush()» в C#, «flush(output)» в Pascal, «sys.stdout.flush()» в Python.