Interactive Chebyshev Search

This is an interactive problem.

You are given three positive integers \(n\), \(k\), and \(r\). In an \(n\)-dimensional space, there is a lattice point \(P(p_1,p_2,\ldots,p_n)\) with each coordinate satisfying \(0 \le p_i \le r\). You are allowed at most \(k\) queries.

In the \(i\)-th query, you choose an integer point \(V_i(v_{i,1},v_{i,2},\ldots,v_{i,n})\) where each \(v_{i,j}\) is in \([0,r]\) and ask whether

\[ \operatorname{dist}(V_i,P) < \operatorname{dist}(V_{i-1},P) \]
holds strictly. Here, the distance \(\operatorname{dist}(A, B)\) is defined as the Chebyshev distance \[ \operatorname{dist}(A,B)=\max_{1\le i\le n}|A_i-B_i| \] with \(A_i\) being the \(i\)-th coordinate of point \(A\).

Special note: For the first query \((i=1)\), if the query is valid the answer is always 0 (which means "no").

Your task is to determine the hidden point \(P\) using at most \(k\) queries.

Interaction details:

• First, you read three positive integers \(n\), \(k\), and \(r\).
• You can then perform queries of the form:
  ? v_{i,1} v_{i,2} \ldots v_{i,n}
  After each query, the judge replies with one of the following:
  • 0: the statement is false, i.e. \(\operatorname{dist}(V_i,P)\) is not strictly less than \(\operatorname{dist}(V_{i-1},P)\).
  • 1: the statement is true, i.e. \(\operatorname{dist}(V_i,P)\) is strictly less than \(\operatorname{dist}(V_{i-1},P)\).
  • -1: your program has been judged as Wrong Answer; in this case, your program must terminate immediately.

  Note: Every query must be followed by a newline and a flush of the output buffer.

• When you have determined \(P\), output the answer in the format:
  ! p_1 p_2 \ldots p_n
  and then terminate your program immediately.

Implementation note: Due to large amounts of I/O, please use fast I/O methods.

inputFormat

The input begins with three positive integers \(n\), \(k\), and \(r\) on one line. In the offline simulation of this interactive problem, the hidden point \(P\) will be provided in the next line as \(n\) integers \(p_1, p_2, \ldots, p_n\).

Note: In the real interactive environment, you will not directly read \(P\). Instead, you must determine \(P\) by making valid queries as described in the problem statement.

outputFormat

Output the coordinates of the hidden point \(P\) in one line in the following format:

! p_1 p_2 \ldots p_n

After outputting the answer, your program should immediately terminate.

sample

1 2 10
5

5

</p>