| Автор: | А. Усманов | Ограничение времени: | 10 сек | |
| Ввод / вывод: | интерактивный | Ограничение памяти: | 256 Мб | |
| Максимальный балл: | 100 |
Данная задача является интерактивной.
После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу. Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли. Конечно это было необходимо из-за событий, которые происходили в фильме. Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств. Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться. То есть деревьям нельзя просто так взять и уйти.
В текущий момент у Шона нет никакой информации о том, где растёт каждое из деревьев. Поэтому он не может с полной уверенностью сказать, что деревья в его лесу неподвижны.
Всего в лесу растёт 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 ≤ 103
1 ≤ L ≤ 109
1 ≤ xi ≤ L
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | ||
|---|---|---|---|---|---|
| N | L | K | |||
| 1 | 14 | N = 1 | 1 ≤ L ≤ 2500 | K = 100 | |
| 2 | 12 | N = 1 | 1 ≤ L ≤ 106 | K = 47 | 1 |
| 3 | 17 | N = 1 | 1 ≤ L ≤ 109 | K = 37 | 1-2 |
| 4 | 15 | 35 ≤ N ≤ 100 | 35 ≤ L ≤ 103 | K = N2 | |
| 5 | 11 | 1 ≤ N ≤ 103 | 1 ≤ L ≤ 104 | K = 100 + 100 * N | 1, 4 |
| 6 | 13 | 1 ≤ N ≤ 103 | 1 ≤ L ≤ 106 | K = 43 * N | 1-2, 4-5 |
| 7 | 18 | 1 ≤ N ≤ 103 | 1 ≤ L ≤ 109 | K = 33 * N | 1-6 |
По запросу сообщается результат окончательной проверки на каждом тесте.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|