Задача I. Interactive and bidirectional ≡

Условие

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

Жюри загадало секретное строку бит X длиной N.

Ваша программа может делать запросы вида "? M L R". Ответ на запрос — результат сравнений в порядке слева-направо и справа-налево двух строк по M бит: начинающейся с позиции L и начинающейся с позиции R. Биты нумеруются справа налево.

Требуется определить значение X, сделав не более ⌈ N + 12⌉ запросов.

Формат входных данных

В первой строке входных данных записано целое число N — количество бит в X.

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

Чтобы сделать запрос, ваша программа должна вывести "? M L R", где M — количество бит для сравнения, а L и R — позиции для сравнения. На каждый запрос программа жюри ответит двумя символами — результат сравнений слева-направо и справа-налево. Возможные результаты сравнения:  < ,  >  и  = . Запросы должны быть такими, что не будет происходить обращения к битам за пределами X.

Когда ваша программа определила X, она должна вывести "! X", где X — строка бит X. После вывода ответа программа должна завершиться.

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

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

Ограничения

1 ≤ N ≤ 60

0 < X < 2^N

1 ≤ M ≤ N

0 ≤ L, R < N

L + M, R + M ≤ N

Пояснение к примерам

В первом примере загадано число 01101. В первом запросе сравнивались 101 с 011 и 101 с 110, поэтому ответ  >  < .

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

5

><

<<

==

? 3 0 2

? 1 1 3

? 2 3 0

! 01101

3

==

? 2 0 1

! 111