24844번 - Guess the Array 다국어인터랙티브

This is an interactive problem. Your program will interact with the jury program using standard input and output.

Alice and Bob have decided to play a game called "Guess the Array". The rules of the game are very simple: Alice has an array of $n$ integers, and Bob has to guess this array by making no more than $n$ queries about the sums on the segments.

In one move Bob can make one of two types of queries to Alice:

1. "? l r" to find out the sum of numbers on the segment of the array from the $l$-th to the $r$-th element inclusive;
2. "!" to tell Alice that he is ready to give the answer. After this query Alice expects $n$ integers from Bob: the initial array.

For each first type query, Alice tells Bob the sum of the numbers in the requested segment. But to make it harder to guess, after each query Alice makes one segment blocked. In further queries, Bob cannot ask for the sum of the numbers on the blocked segments.

Help Bob guess Alice's array by making no more than $n$ first type queries.

The first line of input contains an integer $n$ --- the size of Alice's array ($1 \leqslant n \leqslant 10^4$). It is guaranteed that all numbers in the array do not exceed $10^{9}$ by their absolute values.

Next, a protocol for communicating with the jury program (interactor) is executed.

The interactor expects two types of requests from your program: "? l r" and "!", where $l$, $r$ are integer boundaries of the segment that you want to know the sum at ($1 \leqslant l \leqslant r \leqslant n$). Each query must be followed by a line break. If your program does not follow the query format, your solution may get any verdict (other than OK).

After the first type of query, you must read three integers $s$, $l_b$ and $r_b$ from the standard input --- the sum on the requested segment $s$ and the boundaries of the new blocked segment $[l_b, r_b]$, that can no longer request a sum for ($|s| \leqslant 10^{18}$; $1 \leqslant l_b \leqslant r_b \leqslant n$).

The query of the second type means that your program is ready to give the answer. After the second type query, you should print $n$ integer guessing the initial array.

Note that your program can make no more than $n$ queries of the first type. If this limit is exceeded, or if you try to query the sum of the previously blocked segment, the interactor will print "-1 -1 -1" and will exit with the verdict WA. To avoid getting a TL or IL verdict, your program must terminate with zero exit code after reading "-1 -1 -1" from the input.