Author: | A. Usmanov | Time limit: | 1 sec | |
Input / output: | interactive | Memory limit: | 512 Mb |
This is an interactive problem. You will interact with a jury program by sending and receiving particular messages.
Jury made up a secret bit string X of length N.
Your program must make a queries of the form "? M L R
".
Answer to the query is a result of left-to-right and right-to-left
comparison of two substrings of M bits: starting with position L and staring from position R. Bits are numbered right to left.
You must determine the value of X by making of not more than ⌈ N + 12⌉ queries.
First line of input contains integer N — number of bits in X.
To make a query, your program must output "? M L R
", where
M — number of bits to compare, L and R — positions to compare.
Jury program answers each query with two characters —
results of left-to-right and right-to-left comparisons.
Possible comparison results are: < , > и = .
Queries must not require access to bits outside boundaries of X.
When your program determines X, it must output "! X
",
where X
— string of bits X.
After printing the answer your program must finish execution.
If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds 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() |
1 ≤ N ≤ 60
0 < X < 2N
1 ≤ M ≤ N
0 ≤ L, R < N
L + M, R + M ≤ N
In the first sample secret number is 01101. First query compares 101 with 011 and 101 with 110, thus the answer is > < .
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|