310482: CF1840G1. In Search of Truth (Easy Version)

G1. In Search of Truth (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The only difference between easy and hard versions is the maximum number of queries. In this version, you are allowed to ask at most $2023$ queries.

This is an interactive problem.

You are playing a game. The circle is divided into $n$ sectors, sectors are numbered from $1$ to $n$ in some order. You are in the adjacent room and do not know either the number of sectors or their numbers. There is also an arrow that initially points to some sector. Initially, the host tells you the number of the sector to which the arrow points. After that, you can ask the host to move the arrow $k$ sectors counterclockwise or clockwise at most $2023$ times. And each time you are told the number of the sector to which the arrow points.

Your task is to determine the integer $n$ — the number of sectors in at most $2023$ queries.

It is guaranteed that $1 \le n \le 10^6$.

Input

The input consists of a single integer $x$ ($1 \le x \le n$) — the number of the initial sector.

Output

After you determine the integer $n$ — the number of sectors, you should output "! n" ($1 \le n \le 10^6$). After that the program should immediately terminate.

Note that, printing the answer does not count as a query.

It is guaranteed that the integer $n$ and the numbers of the sectors are fixed initially and will not be changed by the jury program depending on the queries.

Interaction

After reading the description of the input, you may ask queries. Queries can be of two types:

1. "+ k" ($0 \le k \le 10^9$) — ask to move the arrow $k$ sectors clockwise.
2. "- k" ($0 \le k \le 10^9$) — ask to move the arrow $k$ sectors counterclockwise.

After each query, you should read an integer $x$ ($1 \le x \le n$) — the number of the current sector to which the arrow points.

You are allowed to make at most $2023$ queries in total.

If you make too many queries, you will get Wrong answer.

After printing a query or the answer, do not forget to output a the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

ExampleInput

1

5

6

7

2

10

9

8

4

3

1

Output

+ 1

+ 1

+ 1

+ 1

+ 1

+ 1

+ 1

+ 1

+ 1

+ 1

! 10

Note

Hacks

To hack, use the following test format.

In the first line, output a single integer $n$ ($1 \le n \le 10^6$) — the number of sectors.

In the second line, output $n$ different integers $1 \le a_1, a_2, \dots, a_n \le n$ — the numbers of the sectors in clockwise order, the arrow initially points to the sector with the number $a_1$.

题目大意：
这是一个交互式问题。你正在玩一个游戏，圆圈被分成n个扇形，扇形从1到n编号。你在一个相邻的房间里，既不知道扇形的数量也不知道它们的编号。还有一个箭头，最初指向某个扇形。最初，主持人告诉你箭头指向的扇形的编号。之后，你可以最多询问2023次，让主持人将箭头沿逆时针或顺时针移动k个扇形，并且每次都会告诉你箭头指向的扇形的编号。你的任务是确定整数n——扇形的数量，并且最多询问2023次。保证1≤n≤10^6。

输入输出数据格式：
输入：一个整数x（1≤x≤n）——初始扇形的编号。
输出：确定整数n——扇形的数量后，你应该输出 "! n"（1≤n≤10^6）。之后程序应立即终止。

交互：
在阅读输入描述后，你可以提出查询。查询可以是以下两种类型：
1. "+ k"（0≤k≤10^9）——请求将箭头沿顺时针移动k个扇形。
2. "- k"（0≤k≤10^9）——请求将箭头沿逆时针移动k个扇形。
每次查询后，你应该读取一个整数x（1≤x≤n）——箭头当前指向的扇形的编号。
你总共最多可以提出2023次查询。

注意：打印答案不算作查询。题目大意： 这是一个交互式问题。你正在玩一个游戏，圆圈被分成n个扇形，扇形从1到n编号。你在一个相邻的房间里，既不知道扇形的数量也不知道它们的编号。还有一个箭头，最初指向某个扇形。最初，主持人告诉你箭头指向的扇形的编号。之后，你可以最多询问2023次，让主持人将箭头沿逆时针或顺时针移动k个扇形，并且每次都会告诉你箭头指向的扇形的编号。你的任务是确定整数n——扇形的数量，并且最多询问2023次。保证1≤n≤10^6。 输入输出数据格式： 输入：一个整数x（1≤x≤n）——初始扇形的编号。 输出：确定整数n——扇形的数量后，你应该输出 "! n"（1≤n≤10^6）。之后程序应立即终止。 交互： 在阅读输入描述后，你可以提出查询。查询可以是以下两种类型： 1. "+ k"（0≤k≤10^9）——请求将箭头沿顺时针移动k个扇形。 2. "- k"（0≤k≤10^9）——请求将箭头沿逆时针移动k个扇形。 每次查询后，你应该读取一个整数x（1≤x≤n）——箭头当前指向的扇形的编号。 你总共最多可以提出2023次查询。 注意：打印答案不算作查询。