This is an interactive problem.

Scientists are planning to measure the radiation levels of a series of black holes. The radiation level of a black hole is given by an integer from $1$ to $n$. To measure the radiation level of each black hole, a special orbital probe equipped with a radiation sensor is used.

The sensor installed on the probe can answer the following queries: given a value $x$, determine whether the radiation level is greater than or equal to $x$. Unfortunately, due to a software bug, the sensor's answer may be incorrect. Fortunately, after the very first incorrect answer, the sensor of this probe changes its state and provides only correct answers for all subsequent queries.

Scientists want to determine the radiation level of several black holes by performing not too many queries to the sensor of the probe directed at each one.

You are required to write a program that interacts with the jury's program, which simulates the probe sensors, and determines the radiation level of each black hole.

For each run of the solution program, you must solve the problem for several black holes with the same value of $n$. The number of black holes in one run does not exceed $100$ and is not communicated to the solution program.

For each test, the jury has fixed a number $q$ — the maximum number of queries allowed for one black hole. It is guaranteed that $q$ queries are sufficient to solve the problem regardless of the answers given by the jury's program. This number is not communicated to the solution program. The constraints on $q$ in different subtasks are given in the table with information about the scoring system. If the solution program makes more than $q$ queries to the jury's program for one black hole, it receives a "Wrong Answer" result on that test.

Interaction

First, the number $n$ is provided as input — the maximum possible radiation level of a black hole ($1 \le n \le 30\,000$). This number is the same for all black holes investigated in this run. After reading $n$, the solution program must interactively communicate with the jury's program to sequentially determine the radiation level of one or more black holes.

The program must perform queries to the sensor and receive answers about the radiation level. To make a query, the solution program must output a string of the form "? x", where $x$ is a positive integer ($1 \le x \le n$).

In response to the solution program's query, the jury's program provides as input either the string "Yes" if the sensor reports that the radiation level of the black hole is greater than or equal to the value $x$ specified in the query, or the string "No" if the sensor reports that the radiation level of the black hole is less than $x$.

If the solution program has determined the answer to the problem, it must output a string of the form "! x", where $x$ is the sought radiation level of the black hole. If $x$ is the only radiation level that contradicts at most one answer from the jury's program for the given black hole, then the answer for this black hole is considered correct.

After outputting the answer for a black hole, the program must read a string. In the case where it is necessary to proceed to the investigation of the next black hole, the string "Correct" will be provided as input.

If all necessary black holes have been investigated, the string "Done" will be provided as input. In this case, the solution program must terminate.

If an incorrect answer is given for a black hole, the solution program will be forcibly terminated and will receive a "Wrong Answer" result on that test.

It is guaranteed that after each answer from the jury's program, there exists a radiation level value such that the answers to all previously made queries for the given black hole, except possibly one, are correct. The jury's program may adapt its behavior, including choosing which of the already given answers was incorrect and what the radiation level of the investigated black hole is, depending on the queries made by the solution program.

Examples

Input 1

2
Yes
No
Yes
Correct
No
No
Done

Output 1

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

Note 1

In the first example, for the first black hole, it is unknown after the first two queries which of the sensor's answers turned out to be incorrect, so a third query is necessary.

Input 2

3
Yes
Yes
No
Yes
No
Done

Output 2

? 2
? 2
? 3
? 3
? 3
! 2

Note 2

The second example shows one of the possible interaction variants for $n = 3$, which finds the answer in 5 queries. It can be shown that it is impossible to find the answer in 4 queries. In both examples, the solution is tested with the value $q = 30$. Note that the jury's program may give other answers even if the solution makes exactly the same queries as in the example.

Subtasks

In subtasks 3–17, in each test, the value $q$ is equal to the minimum number of allowed queries with which one can guarantee (i.e., by making no more than $q$ queries) to find the radiation level of a black hole regardless of the sensor's answers for the value $n$ in that test.