Задача H. Hard banknote thrower ≡

Условие

Если вы уже прочитали условие задачи E. Easy banknote thrower: условие этой задачи отличается лишь в операции, которую делает банкнотомёт. А именно: операция поразрядного умножения (смотрите Пояснение) вместо операции сложения.

Олег долгое время пользуется услугами банка Деньгофф. Сегодня ему потребовалось метнуть большую сумму денег с карты, но он забыл от неё пин-код. К счастью для компании, банкнотомёты Деньгофф умеют давать подсказки про пин-код.

Во-первых, банкнотомёт сообщает результат сравнения соседних цифр в пин-коде. Например, для пин-кода 0911 получится <>=, а для популярного пин-кода 1234 — <<<.

Во-вторых, можно попробовать ввести в банкнотомёт какой-то пин-код. Если он окажется неправильным, то банкнотомёт выполнит операцию поразрядного умножения правильного и введенного пин-кодов, и сообщит результат сравнения соседних цифр в получившемся числе. Разумеется, после такой операции количество цифр может быть больше, чем в исходном пин-коде. Программисты банка Деньгофф предусмотрели такое переполнение: если новые разряды появились, то для них также выполнится сравнение соседних цифр. Для безопасности пользователей, после 10 попыток ввода неправильного пин-кода карта блокируется.

Помогите Олегу определить пин-код от карты до того, как она заблокируется.

Пояснение

Поразрядным умножением двух чисел называется операция в ходе которой перемножаются цифры стоящие на одних и тех же позициях. То есть происходит перемножение цифр на нулевой позиции, на первой позиции, и т.д. Перенос переполнения в старший разряд выполняется по обычным правилам арифметики.

Более формально, операцию поразрядного умножения можно выразить формулой ∑_i = 0 a_i * b_i * 10ⁱ, где a_i и b_i — цифры на i-й позиции.

Примеры поразрядного умножения представлены на картинке.

Протокол взаимодействия

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

Сначала программа жюри отправляет вашей программе целое число N — количество цифр в пин-коде. Далее, в новой строке отправляется строка из N − 1 символа <, > и = — сравнение соседних цифр в пин-коде.

После этого ваша программа может делать запросы вида "? X", где X — целое число, попытка ввести пин-код, можно выводить без лидирующих нулей. Если пин-код правильный, то программа жюри отвечает вашей программе строкой "ok", после этого ваша программа должна завершиться. Иначе программа жюри отвечает строкой из минимум N − 1 символа <, > и = — сравнение соседних цифр результата операции поразрядного умножения правильного и введенного пин-кодов.

Ваша программа может сделать только 9 запросов с неправильным пин-кодом. Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Если ваша программа сделает недопустимый вывод, то она получит вердикт "Presentation error".

Если ваша программа получила от программы жюри строку "-1", то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Ограничения

2 ≤ N ≤ 18

0 ≤ X < 10^N

Примеры тестов

4
<<>

===

=<>

<>=

=<>

=<>

=<>

=<=

<>>

<>>

ok

? 1000

? 0010

? 0020

? 0012

? 0013

? 0014

? 0015

? 0210

? 0150

? 0451

3
==

>=

>=

>=

<>=

ok

? 100

? 200

? 300

? 400

? 333

18
====<<<<<<<<<====

ok

? 1234567899999