Problem H. Hard banknote thrower ≡

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

Statement

If you have already read the problem statement E. Easy banknote thrower: the task specification for this problem differs only in the operation performed by the banknote thrower. Namely: bitwise multiplication operation (see Explanation) instead of addition operation.

Oleg has been using the services of Moneykoff Bank for a long time. Today, he needs to throw a large sum of money from his card, but he forgot its PIN code. Fortunately for the company, Moneykoff Bank's banknote throwers can provide hints about the PIN code.

Firstly, the banknote thrower reports the result of comparing neighboring digits in the PIN code. For example, for the PIN code 0911, it would be <>=, and for the popular PIN code 1234, it would be <<<.

Secondly, you can attempt to input a PIN code into the banknote thrower. If it proves incorrect, the banknote thrower will perform the operation: bitwise multiplication of the correct and entered PIN codes, and report the result of comparing adjacent digits in the resulting number. Of course, after such an operation, the number of digits may be greater than in the original PIN code. The Moneykoff Bank programmers have anticipated such overflow: if new digits appear, a comparison of neighboring digits will also be performed for them. For user safety, after 10 attempts to enter the wrong PIN code, the card is blocked.

Help Oleg determine the PIN code for the card before it is blocked.

Explanation

Bitwise multiplication of two numbers refers to the operation in which the digits at the same positions are multiplied. That is, the digits at the zeroth position, first position, and so on are multiplied. Overflow is carried out to the higher digit following the regular rules of arithmetic.

More formally, bitwise multiplication can be expressed by the formula i = 0 ai * bi * 10i, where ai and bi are the digits at the i-th position.

Examples of bitwise multiplication are presented in the picture.

Interaction protocol

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

First, the jury's program sends your program an integer N — the number of digits in the PIN code. Then, on a new line, a string of N − 1 characters <, > and = — comparing neighboring digits in the PIN code.

After that, your program can make queries of the form "? X", where X is an integer, an attempt to enter a PIN code, and can be output without leading zeros. If the PIN code is correct, the jury's program responds to your program with the string "ok", after which your program must terminate. Otherwise, the jury's program responds with a string of at least N − 1 characters <, > and = — comparing neighboring digits in the result of bitwise multiplication of the correct and entered PIN codes.

Your program can only make 9 queries with an incorrect PIN code. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

Every query 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()

If your program makes incorrect query, it will receive "Presentation error" verdict.

If your program receives the string "-1" from the jury's program, it must immediately terminate. This is possible if your program violates the interaction protocol. If your program does not terminate, the verdict may differ from those described above (for example, it may be "Runtime error").

2 ≤ N ≤ 18

0 ≤ X < 10N

Sample tests

No. Standard input Standard output
1
4
<<>

===

=<>

<>=

=<>

=<>

=<>

=<=

<>>

<>>

ok



? 1000

? 0010

? 0020

? 0012

? 0013

? 0014

? 0015

? 0210

? 0150

? 0451

2
3
==

>=

>=

>=

<>=

ok



? 100

? 200

? 300

? 400

? 333

3
18
====<<<<<<<<<====

ok



? 1234567899999


0.142s 0.013s 15