18538번 - Medium Hadron Collider 다국어인터랙티브

Okarin Kyouma is a brilliant scientist working on Medium Hadron Collider (MHC) in Société Européenne de Recherche Nucléaire (SERN). His current experiments aim to unravel the mysterious Stein's gate effect.

MHC consists of a sufficiently large amount of sections arranged on a line and numbered $1, 2, 3, \dots$ along the line. Particle beams traverse through sections in ascending order of section numbers, it takes one second for a beam to pass any section. There are two types of beams which may be present in MHC: electronic beams $e^{-}$ and positronic beams $e^{+}$.

Initially, there is a single electronic beam in the beginning of the first section of MHC. Each section is affected by the Stein's gate effect. When a particle beam goes through the center of section $i>1$, the gate is triggered and creates another beam in the center of section $i-1$. This new beam is either the same or inverted (that is, $e^{+}$ instead of $e^{-}$, and vice versa). The new beam moves in the same direction and with the same speed as the initial beam. Beam recreation is coherent: at each step, either all sections produce the same beams or all sections produce inverted beams. 

Then created beam interferes with the one already present in the section, if any. Beams of the same type merge, while beams of opposite types annihilate. Formally, we may say that a single electronic beam has charge $-1$, single positronic beam has charge $+1$, and an "empty" beam has charge $0$. The result of collision of beams with charges $\alpha$ and $\beta$ will be a beam with charge $\gamma = \alpha + \beta$. Here are a few examples:

• A single electronic beam colliding with a single positronic beam leave an "empty" beam.
• Two single positronic beams become a "double" positronic beam with total charge $+2$.
• A positronic beam with total charge $+5$ colliding with an electronic beam with total charge $-8$ become an electronic beam with total charge $-3$.

The end of the $N$-th second of experiment approaches. So, the Stein's gate effect was activated exactly $N-1$ times, but the initial electronic beam is yet in the section numbered $N$. Okarin wants to measure the total charge of beams traversing through some sections but, unfortunately, measurement tools for sections $1$ through $128$ are out of reach. Okarin needs these values urgently, but he only has time to check the measurements in at most $10$ sections. Moreover, he does not have proper permission to get measurements in sections beyond number $512$, thus he may only ask about sections from $129$ to $512$ inclusively.

You need to help Okarin recover measures in sections from $1$ to $128$. Note that detectors in sections are not perfect, and can only show $7$ digits and the sign. Thus, for example, if a detector approaches $+10\,000\,000$, it will show $-9\,999\,999$ instead. After that, $+10\,000\,001$ will be shown as $-9\,999\,998$, and so on.

The first line of input contains a single integer $N$ which is the number of seconds passed since the start of the experiment. All actual test cases will have $N=10^7$.

After reading $N$, you may make queries in the form of "? $x$" on a single line, where the integer $x$ ($129 \leq x \leq 512$) is the number of section you are interested in. In return, you will get a single integer $c$ ($-10^7 < c < 10^7$) which is equal to the total charge of beams currently located in section $x$, as shown by the detector. You may make at most $10$ queries.

When you are ready, output the answer in the form of "! $c_{1}$ $c_{2}$ $\dots$ $c_{128}$" on a single line, where $c_i$ is the total charge of the beam in the $i$-th section. Numbers should be formatted in the same way as detector measures (that is, $-10^7 < c_i < 10^7$).

The example for this problem has $N=4$ and does not coincide with the actual first test case. In the example, the Stein's gate effect was activated three times. Let us assume that its first and second activations produced the same beams, and the third activation produced inverted beams. Then:

1. Initially, there is a single beam with charge $-1$ in the first section.
2. After $1.5$ seconds, the initial beam goes through the center of the second section and is recreated in the center of the first section. At this moment, we have beams with charges $-1$ in the centers of first and second sections.
3. After $2.5$ seconds, the initial beam goes through the center of the third section, while its copy goes through the center of the second section. Both beams are recreated the same in preceding sections. Then the first copy of the initial beam in the second section interferes with the new copy. After that, we have beams with total charges $-1$, $-2$ and $-1$ in the centers of first, second, and third sections correspondingly.
4. After $3.5$ seconds, beams once again pass centers of sections. But this time, they are recreated with inverted signs. After all collisions, we will have a beam with charge $+1$ in the first section, a beam with charge $+1$ in the second section, a beam with charge $-1$ in the third section, and a beam with charge $-1$ in the fourth section.

In the example, the solution asks what are the charges in sections from $1$ to $5$, and then outputs the charges in sections from $1$ to $4$.
Recall that, in the actual test cases, the solution can ask only about sections $129$ to $512$, and must then output the measurements in sections $1$ to $128$.