시간 제한메모리 제한제출정답맞힌 사람정답 비율
12 초 (추가 시간 없음) 256 MB0000.000%

문제

This is an interactive problem.

John has an array of $n$ mysterious integers. He has an access to a magic box that can combine two integers into one. Let $x \circ y$ be the result of combining two integers, $x$ and $y$, with this magic box. After a lot of experiments, John has noticed that the magic box has the following properties:

  • $x \circ y = y \circ x$
  • $x \circ (y \circ z) = (x \circ y) \circ z$

John has $q$ cousins, and each of them likes all the integers in his array except some $k$ of them. John wants to give gifts to all his cousins, so he wants to give each cousin the combination of all his integers except the $k$ this cousin doesn't like.

John likes his cousins, but his magic box is old and worn off because of his intense experiments. He is willing to use the box at most $4 (n + q + q \cdot k)$ times. Help him get all the required combinations!

인터랙션 프로토콜

Initially, you are given a line containing three integers $n$, $q$ and $k$ ($1 \le q \le n \le 2000$, $n \ge 3$, $2 \le 2^k \le n$). Next, you are given a line containing $n$ integers $a_1, \ldots, a_n$ ($0 \le a_i < 2^{50}$). After that, you can use three types of queries (each query must be written on a separate line):

  • "? $x$ $y$" where $x$ and $y$ are integers ($0 \le x, y < 2^{50}$). A query of this type asks to use the magic box. The response to this query is a line containing the integer $x \circ y$ ($0 \le x \circ y < 2^{50}$). You can only use a query of this type $4 (n + q + q \cdot k)$ times in total. If you exceed this amount, the jury program will print "-1", and after that, the checking will be terminated.
  • "next". A query of this type asks for the indices of $k$ integers which the next cousin does not like. The response to this query is a line containing $k$ distinct integers $d_1, \ldots, d_k$ ($1 \le d_i \le n$): the indices of elements which this cousin does not like. You can only use a query of this type again after you answer the previous such query.
  • "! $x$" where $x$ is an integer ($0 \le x < 2^{50}$). Here, $x$ should be the integer John will give to the last described cousin (that is, the cousin corresponding to the most recent "next" query). There is no response for a query of this type.

To prevent output buffering, flush the output buffer after each printed line: this can be done by using, for example, fflush (stdout) in C or C++, System.out.flush () in Java, flush (output) in Pascal, or sys.stdout.flush () in Python. Also, do not forget to terminate each line of output with a newline character.

예제 입력 1

3 3 1
0 1 0

1

1


2

0


3

예제 출력 1



next

? 1 0

! 1
next

? 0 0

! 0
next

! 1

노트

In each test, the rules for the magic box are fixed and don't depend on your queries. Different rules are used for different tests. It is guaranteed that the magic box satisfies the conditions from the problem statement.

In the sample test, the operation performed by the magic box is assumed to be bitwise OR.

채점 및 기타 정보

  • 예제는 채점하지 않는다.