Это интерактивная задача.

В прекрасной Метрополии будущего необходимость в машинистах, управляющих поездами метро, отпала. Благодаря развитию технологий, их заменил искусственный интеллект (ИИ). К сожалению, в один прекрасный день опасения писателей-фантастов сбылись — ИИ взбунтовался, и теперь где-то в метро ездит неуправляемый поезд. Страшно представить, чем это грозит городской транспортной системе! Ваша задача состоит в том, чтобы найти поезд в сложной системе метро и остановить неуправляемый ИИ.

Метро Метрополии представляет из себя одну ветку (обычную прямую ветку без самопересечений) из $$$n$$$ станций, последовательно пронумерованных от $$$1$$$ до $$$n$$$. В каждый момент времени поезд находится ровно на одной из этих станций. Ваша задача — найти номер этой станции.

Для определения нужной станции диспетчер Сара одолжила вам устройство, позволяющее вам выбрать произвольные числа $$$l$$$ и $$$r$$$ ($$$l \le r$$$), после чего оно проверит, верно ли, что поезд находится на станции с номером между $$$l$$$ и $$$r$$$ включительно. К сожалению, для перезарядки устройства требуется некоторое время (и вы используете его, как только перезарядка завершается), поэтому между двумя применениями поезд может перебраться из той станции, где он сейчас находится, в любую станцию с номером, отличающимся не более чем на $$$k$$$. Формально, если при некотором применении устройства поезд находился на станции $$$x$$$, то при следующем применении он может находиться на любой станции $$$y$$$ такой, что $$$\max(1, x - k) \leq y \leq \min(n, x + k)$$$. При этом ИИ не знает, что вы пытаетесь поймать поезд, и перемещает поезд согласно некоторому заранее составленному им плану.

В процессе изучения устройства вы выяснили, что оно было сделано очень давно и сможет выдержать не более чем $$$4500$$$ использований, после чего оно сломается, а ваша задача будет считаться проваленной.

Сможете ли вы найти станцию, на которой находится поезд за не более чем $$$4500$$$ использований устройства?

Вы можете использовать устройство не более $$$4500$$$ раз. Чтобы использовать устройство, вы должны вывести через пробел два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$). В ответ на это вы получите либо строку «Yes», если между станциями с номерами $$$l$$$ и $$$r$$$ включительно находится поезд, либо строку «No» в противном случае. Если $$$l = r$$$, и вы получили ответ «Yes», это значит, что вы точно определили станцию, на которой находится поезд, и ваша программа после этого должна немедленно завершиться.

Ответ «Bad» вместо «Yes» или «No» означает, что ваша программа сделала некорректный запрос или превысила ограничение на число запросов. Ваша программа должна немедленно завершиться после прочтения ответа «Bad», вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы

Чтобы взломать решение, представьте тест в следующем формате.

Первая строка должна содержать три целых числа $$$n$$$, $$$k$$$ и $$$p$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le k \le 10$$$, $$$1 \le p \le n$$$) — количество станций, максимальное количество станций, на которое может переместиться поезд между использованиями устройства и начальная позиция поезда, соответственно.

Каждая из следующих $$$4500$$$ строк должна содержать одно целое число $$$x$$$ ($$$1 \le x \le n$$$) — позицию поезда после очередного запроса. Две последовательных позиции не должны отличаться более, чем на $$$k$$$.

Например, следующие строчки образуют начало теста из примера.

10 2 5
5
3
5
7
7
...