시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB124457.143%

문제

This is an interactive task.

Small Tuple and her brother Kortesh live happily in their $d$-dimensional world. Today they came up with an idea to play hide-and-seek -- Kortesh will be the first seeker. As finding people in large-dimensional worlds is usually quite a difficult task, they decided to use their walkie-talkies for communication. Moreover, each of them took their GPS receivers.

Tuple hid in one of the points of the Hypercube Forest and is not going to move until Kortesh finds him. The forest is a hypercube with its side equal to $r$ -- it contains all $d$-dimensional points whose coordinates are integers from $[0, r]$. Kortesh walks round the forest and once in a time uses his walkie-talkie and tells Tuple his current location. Then, Tuple responds with a single word: hotter if Kortesh came closer to Tuple since their last (i.e., the most recent) communication, or colder otherwise.

Given $d$-dimensional points $p, x, y$, Tuple says that $x$ is closer to $p$ than $y$ if \[ \max_{i = 1, 2, \ldots, d} |x_i - p_i| < \max_{i = 1, 2, \ldots, d} |y_i - p_i|. \]

Unfortunately, Kortesh forgot to charge his walkie-talkie and the battery will allow him only for $100d$ communications. Help him find his sister before he loses the ability to contact her.

프로토콜

Initially, your program should read the two integers $d$ and $r$ (defined as above; $1\leq d\leq 100$, $2\leq r\leq 10^9$) from standard input.

Your program should then use standard input and standard output to communicate with Tuple.

Tuple is hidden in a point with integer coordinates; each coordinate is in the interval $[0, r]$. She never moves and always responds truthfully.

In order to move to the point $x=(x_1,\ldots,x_d)$ (where each $x_i$ is an integer from $[0,r]$) and report that position to Tuple, print a single line formatted in the following way.

  • $\texttt{?}$ $x_1$ $x_2$ $\ldots$ $x_d$

Afterwards, you can read Tuple's response from the input. The response always consists of a single line and contains a single word, either "hotter" or "colder". If this is the first time Kortesh communicates with Tuple, the response will necessarily be "colder". Otherwise, the response is "hotter" if and only if the point $x$ is closer to Tuple than $x'$, where $x'$ is Kortesh's location when they last communicated.

You can communicate with Tuple at most $100d$ times.

Once you have determined Tuple's position to be $p=(p_1,\ldots,p_d)$, print a single line formatted in the following way and terminate your program.

  • $\texttt{!}$ $p_1$ $p_2$ $\ldots$ $p_d$

Do not forget to flush the standard output after printing each line.

예제 입력 1

2 2
? 2 2
? 0 0
? 1 1
? 2 2
! 2 2

예제 출력 1

colder
colder
hotter
hotter

채점 및 기타 정보

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