310483: CF1840G2. In Search of Truth (Hard Version)

G2. In Search of Truth (Hard 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 $1000$ 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 $1000$ 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 $1000$ 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 $1000$ 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编号。你在一个相邻的房间里，既不知道扇形的数量也不知道它们的编号。还有一个箭头，最初指向某个扇形。最初，主持人告诉你箭头指向的扇形的编号。之后，你可以最多询问1000次，让主持人将箭头逆时针或顺时针移动k个扇形，并且每次都会告诉你箭头指向的扇形的编号。你的任务是确定整数n——扇形的数量，并且最多询问1000次。保证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）——箭头当前指向的扇形的编号。
你总共最多可以进行1000次查询。

如果查询次数过多，你将得到“错误答案”。
在打印查询或答案后，不要忘记输出换行符并刷新输出。否则，你将得到“空闲时间超过限制”。在C++中，使用 fflush(stdout) 或 cout.flush()；在Java中，使用 System.out.flush()；在Pascal中，使用 flush(output)；在Python中，使用 stdout.flush()；其他语言的文档中有说明。

示例：
输入：
1
5
6
7
2
10
9
8
4
3
1
输出：
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
! 10

注意：
要破解，请使用以下测试格式。
在第一行，输出一个整数n（1≤n≤10^6）——扇形的数量。
在第二行，输出n个不同的整数1≤a1,a2,…,an≤n——顺时针方向的扇形编号，箭头最初指向编号为a1的扇形。题目大意： 这是一个交互式问题。你正在玩一个游戏，圆圈被分成n个扇形，扇形从1到n编号。你在一个相邻的房间里，既不知道扇形的数量也不知道它们的编号。还有一个箭头，最初指向某个扇形。最初，主持人告诉你箭头指向的扇形的编号。之后，你可以最多询问1000次，让主持人将箭头逆时针或顺时针移动k个扇形，并且每次都会告诉你箭头指向的扇形的编号。你的任务是确定整数n——扇形的数量，并且最多询问1000次。保证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）——箭头当前指向的扇形的编号。 你总共最多可以进行1000次查询。 如果查询次数过多，你将得到“错误答案”。 在打印查询或答案后，不要忘记输出换行符并刷新输出。否则，你将得到“空闲时间超过限制”。在C++中，使用 fflush(stdout) 或 cout.flush()；在Java中，使用 System.out.flush()；在Pascal中，使用 flush(output)；在Python中，使用 stdout.flush()；其他语言的文档中有说明。 示例： 输入： 1 5 6 7 2 10 9 8 4 3 1 输出： + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 ! 10 注意： 要破解，请使用以下测试格式。 在第一行，输出一个整数n（1≤n≤10^6）——扇形的数量。 在第二行，输出n个不同的整数1≤a1,a2,…,an≤n——顺时针方向的扇形编号，箭头最初指向编号为a1的扇形。