C. 28 stab wounds
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem

Imagine that you find yourself as an investigator in a well-known game. You need to expose $$$n$$$ deviants who have committed outrageous crimes. Each android $$$i$$$ has a punishment measure $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$, $$$a_i$$$ is an integer) and a stress parameter $$$c_i$$$, initially equal to zero. Since we have little time, you will conduct a parallel interrogation. With one question, you can shout aloud (all non-confessing deviants will hear your statement) "$$$X$$$ STAB WOUNDS! You didn't want to leave him a chance, huh?" Each deviant perceives this statement personally and starts to think:

  • If $$$X \gt a_i$$$, the deviant will be sure that you do not know that he committed a crime and are just guessing, so after this, he will stop responding to any questions.
  • If $$$X \le a_i$$$, the deviant receives $$$X$$$ units of stress because he is sure that you are about to uncover his sins. That is, $$$c_i := c_i + X$$$ (the value of $$$c_i$$$ increases by $$$X$$$).
After any question, if the stress level $$$c_i$$$ is at least the measure of punishment, he will confess and start giving up everyone, but he will do it cunningly: he will name the sum of the punishments of himself and another deviant. More formally, when it holds that $$$c_i \ge a_i$$$, android $$$i$$$ will say for each accomplice $$$j$$$ the number $$$a_i + a_j$$$, $$$i \neq j$$$.

When a deviant confesses, he leaves the interrogation room and does not hear any further questions.

Your task is to ensure that all deviants confess, and also to find out their measures of punishment. If at least one deviant does not confess, you will receive a Wrong Answer verdict even if you output the correct measures of punishment. Also, in some subgroups, you will not be required to find out the measures of punishment; it is enough to ensure that everyone confesses.

Input

A single line contains three integers $$$n$$$, $$$k$$$, $$$t$$$ ($$$3 \le n \le 100$$$, $$$30 \le k \le 1000$$$, $$$0 \le t \le 1$$$) — the number of deviants in the precinct, the maximum number of questions that can be asked, and a parameter that determines whether you need to output all measures of punishment or just ensure that everyone confesses.

Interaction

In this problem, you can ask questions of two types:

  • "$$$?$$$ $$$X$$$" ($$$1 \le X \le 10^9$$$). You make an accusation with $$$X$$$ stabs.

    After each query, the interactor returns the following data:

    In the first line, the number $$$m$$$ ($$$0 \le m \le n$$$), the number of deviants who want to confess.

    In the next $$$m$$$ lines, $$$n + 1$$$ numbers are given: $$$j$$$ and $$$n$$$ numbers $$$b_i$$$, where $$$b_i = a_j + a_i$$$ for all $$$j \neq i$$$. For $$$i = j$$$, $$$b_i = 0$$$. The number of the confessing deviant and information about accomplices, respectively.

    It is guaranteed that each deviant, if they confess, will confess only once.

  • "$$$!$$$ $$$a_1\ a_2\ \dots\ a_n$$$". This question means that you are ready to state all measures of punishment, and the interrogation ends, and your program must terminate immediately. If not all deviants confessed, you will receive a Wrong Answer verdict. All numbers you output $$$a_i$$$ must be integers, and it must also hold that $$$0 \le a_i \le 10^9$$$ ($$$0$$$ means that you do not know the measure of punishment). If at least one number is not an integer or outside this range, you will receive a Wrong Answer verdict. Also, if $$$t = 1$$$ and you output at least one incorrect measure of punishment, you will receive a Wrong Answer verdict.

    After making this query, your program must terminate.

You can make no more than $$$k$$$ queries of the first type and only one query of the second type. Even if you made all androids confess, but cannot determine their measures of punishment, the program must terminate with a query of the second type.

The interactor in this problem is non-adaptive.

After outputting each query, do not forget to output a newline and flush the output buffer. Otherwise, you will receive a verdict of "Idleness Limit Exceeded" To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Scoring
№Additional constraintsPointsRequired groupsComment
$$$k$$$$$$a_i$$$$$$t$$$
$$$0$$$—————Tests from the statement
$$$1$$$$$$k = \max(n, 30)$$$—$$$t=0$$$$$$6$$$—$$$a_1 = 1$$$
$$$2$$$$$$t=1$$$$$$7$$$$$$1$$$
$$$3$$$$$$k = 1000$$$$$$a_i \le 1000$$$$$$ t=0$$$$$$9$$$——
$$$4$$$$$$t=1$$$$$$10$$$$$$3$$$
$$$5$$$$$$a_i \le 5 \cdot 10^5$$$$$$t = 0$$$$$$10$$$$$$3$$$—
$$$6$$$$$$t=1$$$$$$11$$$$$$3-5$$$
$$$7$$$$$$k = 30$$$—$$$t=0$$$$$$8$$$—$$$a_i$$$ — power of two
$$$8$$$$$$t=1$$$$$$8$$$$$$7$$$
$$$9$$$$$$t=0$$$$$$15$$$$$$1,3,5,7$$$—
$$$10$$$$$$t=1$$$$$$16$$$$$$0-9$$$
Examples
Input
4 30 0

1
1 0 8 7 9

3
2 8 0 9 11
3 7 9 0 10
4 9 11 10 0
Output

? 3


? 3




! 0 0 0 0
Input
4 30 1

1
1 0 8 7 9

3
2 8 0 9 11
3 7 9 0 10
4 9 11 10 0
Output

? 3


? 3




! 3 5 4 6
Note

Let's analyze what happens in the example:

First, "3 stabs" was shouted. The first deviant confessed since his stress reached his measure of punishment ($$$0 + 3 \ge 3$$$). The stress of all androids: $$$3$$$, $$$3$$$, $$$3$$$, $$$3$$$.

Next, "3 stabs" was shouted again. All deviants confessed because their stresses reached $$$6$$$. Accordingly, $$$3 + 3 \ge 5$$$, $$$3 + 3 \ge 4$$$, $$$3 + 3 \ge 6$$$ for the second, third, and fourth deviants.

Since everyone confessed, we can output the measures of punishment. They turned out to be $$$3$$$, $$$5$$$, $$$4$$$, and $$$6$$$.

Note that empty lines are left only for visual interaction; they do not need to be output.