This is an interactive problem. The query limit is $18\,000$ queries.

The jury has a secret string which consists of exactly 1000 binary digits. In each test for this problem, the string is fixed in advance and does not change. You have to find this string using queries.

In each query, you choose a segment $[a, b]$ ($1 \le a \le b \le 1000$) to ask about. Then the jury flips a coin, and gives you one of the two values, each with probability of 50%:

1. The number of 1s in the segment $[a, b]$;
2. A value from $0$ to $b - a + 1$ which is not equal to the number of ones on this segment, chosen uniformly at random.

You are not allowed to use the same query twice. All random values used in this problem are uniform and independent.

Interaction

The participant program must interact with the jury program by printing commands in one of the following formats:

• ? a b. A query for the segment $[a, b]$. To answer this query, the jury program will output a single integer which will, with probability 50%, be either the number of 1s in the segment $[a, b]$ or a random value from $0$ to $b - a + 1$ not equal to it.
• ! ans. The answer to the problem, where ans is a string of length 1000 consisting of 0s and 1s. After this command, the participant program should terminate immediately.

Examples

Input 1

2
3
3
1
3

Output 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

Note

The example above is given only to demonstrate the format. In this example, the string has length 5. In the real first test, as well as all other tests, the length of the string to guess is exactly 1000.