C. Восстановление массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Вам нужно использовать операцию flush после вывода каждого запроса. Например, в C++ вы должны использовать функцию fflush(stdout), в Java — использовать System.out.flush(), а в Паскале — flush(output).

В этой задаче вам надо восстановить массив, который заранее вам неизвестен. Вы можете считать, что жюри загадало некоторый массив a, про который вам известна только его длина n.

Единственное допустимое действие — узнать сумму пары элементов, указав их индексы i и j (индексы должны быть различными). В результате запроса для индексов i и j вы получите сумму ai + aj.

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

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

Каждый тест в этой задаче состоит из одного массива, который ваша программа должна восстановить.

В первой строке входных данных следует целое положительное число n (3 ≤ n ≤ 5000) — длина загаданного массива. В первую очередь ваша программа должна прочитать это число.

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

  • В случае, если программа осуществляет запрос на сумму, то следует вывести строку вида «? i j» (i и jразличные целые числа от 1 до n) — индексы элементов массива, сумму которых ваша программа запрашивает.
  • В случае, если программа сообщает восстановленный массив, то следует вывести строку вида «a1 a2 ... an» (гарантируется, что все ai в правильно восстановленном массиве — положительные целые числа и не превосходят 105), где ai равно числу, стоящему в массиве в позиции i.

Результатом запроса на сравнение является единственное целое число, равное ai + aj.

Для массива длины n ваша программа должна сделать не более n запросов на сумму. Обратите внимание, что вывод строки вида «a1 a2 ... an» не считается запросом и не учитывается при подсчете их количества.

Не забывайте использовать операцию flush после каждой выведенной строки.

После вывода ответа ваша программа должна завершиться.

Пример
Входные данные
5
 
9
 
7
 
9
 
11
 
6
 
Выходные данные
 
? 1 5
 
? 2 3
 
? 4 1
 
? 5 2
 
? 3 4
 
! 4 6 1 5 5
Примечание

Вы можете взламывать, задавая тесты следующего вида:

  • в первой строке должно быть записано целое число n (3 ≤ n ≤ 5000) — длина массива,
  • во второй строке должны быть записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 105) — элементы загаданного массива.