Recover the Hidden Array

Mingyue has determined an integer sequence \(a\) of length \(n\) where each element \(a_i\) satisfies \(|a_i| \le 10^6\) for \(1 \le i \le n\). The sequence is fixed at the beginning.

Qingfeng is only given the value of \(n\) but does not know the elements of \(a\). He is allowed to perform at most \(10^4\) queries. In each query, he specifies an interval \([l, r]\) (with \(1 \le l \le r \le n\)) and the values in this interval are multiplied by \(-1\) permanently. After each query, Mingyue reveals the maximum subarray sum of the current sequence. The maximum subarray sum is defined as the maximum possible sum of any contiguous subarray (which may be empty, in which case the sum is considered \(0\)).

The goal is to determine the original sequence \(a\). Moreover, Qingfeng is only allowed to output his answer once (i.e. one final output of the recovered sequence). Note that your score may depend on the number of queries you make.

Interaction Protocol:

• The first input line contains the integer \(n\).
• You can then issue several queries by printing a line in the format: ? l r (remember to flush your output after printing).
• After each query, you will receive an integer \(M\) representing the maximum subarray sum of the current sequence after applying the query.
• When you are ready, output your final answer in the following format: ! a_1 a_2 \dots a_n and immediately terminate your program.

Note for Implementation: Since this is an interactive problem, ensure that you flush the output after printing each query or the final answer. For example, in C++ using std::cout << std::flush or in Python using sys.stdout.flush().

inputFormat

The first line of input contains a single integer \(n\), the length of the sequence.

In an interactive scenario, after your queries the interactor will respond with an integer \(M\) for each query (the maximum subarray sum after the operation). However, in our test cases, the full sequence is provided after \(n\) for simulation purposes.

outputFormat

Your program should perform queries (if any) following the format ? l r and flush the output immediately. When you are ready to provide your final answer, output a single line in the format:

! a_1 a_2 ... a_n

After printing the final answer, terminate your program.

sample

3
1 -2 3

! 1 -2 3