Problem F. Interactive increment

Author:A. Usmanov   Time limit:1 sec
Input / output:interactive   Memory limit:256 Mb

Statement

This is an interactive problem.

Jury has chosen a secret integer X consisting of exactly N bits. It is known that the number contains K bits '1' and N − K bits '0'. Your program can make queries of the form "+ Y", which causes current value of X to be increased by integer Y. Bits higher than N-th are truncated, so actual operation is X = (X + Ymod 2N.

Jury's program answers every query with number of '1' bits in the current value of X. Your program must determine current value of X by making no more than ⌊ N2 queries.

Input format

First line of input contains two integers N and K — total number of bits in the value and number of '1' bits in the starting value.

Interaction protocol

To make a query, your program must output "+ Y", where Y — integer to be added to X. For every query jury's program will reply with a single integer — number of '1' bits in the value of X after executing the request.

When your program determines current value of X, it must output "! X" and stop.

If your program will make incorrect query, it will receive "Presentation error" verdict. If your program will exceed allowed number of queries, it will receive "Wrong answer" verdict.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Language C++ Pascal Java Python
Code cout.flush() flush(output) System.out.flush() stdout.flush()

Constraints

1 ≤ N ≤ 60

0 ≤ K ≤ N

0 ≤ X, Y < 2N

Note for samples

In the first sample jury has chosen number 13 (1101 in binary). After the first query the value is (13 + 9mod 16 = 6 (01102). After the second query the value is (6 + 9mod 16 = 15 (11112).

Sample tests

No. Standard input Standard output
1
4 3 

2

4

+ 9

+ 9

! 15
2
2 2

! 3

0.138s 0.019s 15