Codeforces Round 764 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

constructive algorithms

interactive

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Interacdive Problem

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThis problem is interactive.

We decided to play a game with you and guess the number $$$x$$$ ($$$1 \le x < n$$$), where you know the number $$$n$$$.

You can make queries like this:

- + c: this command assigns $$$x = x + c$$$ ($$$1 \le c < n$$$) and then returns you the value $$$\lfloor\frac{x}{n}\rfloor$$$ ($$$x$$$ divide by $$$n$$$ and round down).

You win if you guess the current number with no more than $$$10$$$ queries.

Interaction

The interaction begins by reading an integer $$$n$$$ ($$$2 < n \le 1000$$$), which is written in the input data on its own line.

Then you can make no more than $$$10$$$ queries. To make a query, print on a separate line:

- + c: this command will assign $$$x = x + c$$$ ($$$1 \le c < n$$$) and then print $$$\lfloor\frac{x}{n}\rfloor$$$ (divide $$$x$$$ by $$$n$$$ and round down) on a separate line.

Print the answer, like the queries, on a separate line. The answer doesn't count in number of queries. To output it, use the following format:

- ! x: the current value of $$$x$$$.

After that, your program should exit.

You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Note that the interactor is not responsive.

To make a hack, use the following format: a single line must contain two numbers $$$x$$$ and $$$n$$$, separated by a space.

Examples

Input

3 1

Output

+ 1 ! 3

Input

5 0 0 1

Output

+ 1 + 1 + 1 ! 5

Input

10 0 0 1 2

Output

+ 2 + 2 + 3 + 8 ! 20

Note

In the first sample initially $$$x = 2$$$. After the first query $$$x = 3$$$, $$$\lfloor\frac{x}{n}\rfloor = 1$$$.

In the second sample also initially $$$x = 2$$$. After the first query $$$x = 3$$$, $$$\lfloor\frac{x}{n}\rfloor = 0$$$. After the second query $$$x = 4$$$, $$$\lfloor\frac{x}{n}\rfloor = 0$$$. After the third query $$$x=5$$$, $$$\lfloor\frac{x}{n}\rfloor = 1$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 08:47:51 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|