Это интерактивная задача. Вам нужно использовать операцию 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 после каждой выведенной строки.
После вывода ответа ваша программа должна завершиться.
Примечание
Вы можете взламывать, задавая тесты следующего вида:
- в первой строке должно быть записано целое число n (3 ≤ n ≤ 5000) — длина массива,
- во второй строке должны быть записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 105) — элементы загаданного массива.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
9
7
9
11
6
|
? 1 5
? 2 3
? 4 1
? 5 2
? 3 4
! 4 6 1 5 5
|