Problem I. Interactive and bidirectional

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.

Input format

First line of input contains integer N — number of bits in X.

Interaction protocol

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

Notes on samples

In the first sample secret number is 01101. First query compares 101 with 011 and 101 with 110, thus the answer is ><.

Sample tests

No. Standard input Standard output




? 3 0 2

? 1 1 3

? 2 3 0

! 01101


? 2 0 1

! 111

0.136s 0.021s 17