Задача G. Тяжелая химия 2 ≡

Условие

Данная задача является интерактивной.

Сегодня Никита принёс на урок по химии весы с двумя чашами. Собрав вокруг себя весь класс, он стал хвастаться о том, как ловко с их помощью он может определять вес любых предметов. У Никиты помимо весов также есть набор полых гирек. Они могут принять любой вес, если наполнить их определённым количеством воды.

Для честной демонстрации своих навыков Никита одолжил у одноклассницы атом какого-то химического элемента весом N нанограммов. Он разместил его на левой чаше весов и теперь собирается класть гирьки на левую и правую чаши, пока не сможет точно назвать вес атома.

Никита понимает, что демонстрация не будет достаточно эффектной, если атом будет весить очень мало, а он положит на весы слишком много гирек. Поэтому он хочет использовать не более ⌈ log₂(N)⌉  + 10 гирек. Помогите Никите определить вес атома.

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

Чтобы положить гирьку, ваша программа должна вывести запрос "L X" или "R X", где X — вес гирьки, которую Никите нужно положить на соответствующую чашу весов. После каждого запроса программа жюри ответит одним из символов " < ", " > " или " = ", если в результате добавления гирьки правая чаша перевесит, левая чаша перевесит или веса чаш сравняются соответственно.

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

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

Если ваша программа в какой-то момент получила символ "!", то это значит, что был нарушен протокол взаимодействия. После этого ваша программа должна немедленно завершиться. В противном случае возможно неверное отображение итогового вердикта.

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

Ограничения

1 ≤ N, X ≤ 2⁵⁵

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

В первом примере суммарный вес на чашах изменялся следующим образом: (5, 0), (5, 4), (5, 8), (11, 8), (11, 12), (12, 12).

Всего в первом примере решение могло использовать не более ⌈ log₂(5)⌉  + 10 = 13 гирек.

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

>

<

>

<

=

R 4

R 4

L 6

R 4

L 1

! 5

<

>

R 14

L 2

! 13