Задача Z. Отрезок деревьев ≡

Условие

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

После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу. Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли. Конечно это было необходимо из-за событий, которые происходили в фильме. Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств. Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться. То есть деревьям нельзя просто так взять и уйти.

В текущий момент у Шона нет никакой информации о том, где растёт каждое из деревьев. Поэтому он не может с полной уверенностью сказать, что деревья в его лесу неподвижны.

Всего в лесу растёт N деревьев. Лес является непрерывным отрезком на прямой от 1 до L. Все деревья растут в разных целочисленных точках.

У Шона есть сканер, который позволяет определить наличие хотя бы одного дерева на каком-то участке леса. К сожалению, заряда сканера хватит только на K сканирований.

Необходимо помочь Шону определить местоположение всех деревьев в лесу. Можно считать, что все сканирования Шон совершает в течение одного дня. За столь короткий промежуток времени рядом с лесом не могло произойти никаких событий, которые заставили бы деревья просто так взять и уйти.

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

Сначала на вход программе-решению подаётся целое число L — длина леса.

Для каждого теста жюри зафиксировало числа N и K — количество деревьев и максимальное количество запросов на сканирование участка леса. Гарантируется, что K запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе-решению. Ограничения на N и K в различных подзадачах приведены в таблице системы оценивания. Если решение делает более K запросов к программе жюри, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы сделать запрос программа-решение должна вывести строку вида "? l r", где l и r (1 ≤ l ≤ r ≤ L) — целые числа, крайние левая и правая точка сканируемого участка леса. В ответ на запрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, есть ли хотя бы одно дерево в запрашиваемом участке.

Если программа-решение определила ответ на задачу, она должна вывести две строки: в первой "ok?", во второй N целых чисел — список точек, в которых растут деревья в порядке возрастания координат. После этого программа-решение должна завершиться.

Гарантируется, что в каждом тесте положение всех деревьев является фиксированным, и не меняется в зависимости от запросов, произведенных программой-решением.

После каждого запроса и вывода ответа необходимо выполнить сброс буфера. Например, в Pascal необходимо написать flush(output), в C++ — cout.flush().

Ограничения

1 ≤ N ≤ 10³

1 ≤ L ≤ 10⁹

1 ≤ x_i ≤ L

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

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

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

5

Yes

No

Yes

No


ok

? 1 5

? 1 2

? 3 3

? 4 5

ok?
3

6

Yes

No

Yes

No

Yes

Yes

Yes


ok

? 1 2

? 1 1

? 2 2

? 3 4

? 5 6

? 5 5

? 6 6

ok?
2 5 6