E. Алеся и дискретная математика
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем функцию хорошей, если ее область определения — целые числа, и если для любого $$$x$$$ из области определения верно, что если в $$$x-1$$$ функция определена, то $$$f(x) = f(x-1) + 1$$$ либо $$$f(x) = f(x-1)$$$

Таня нашла $$$n$$$ хороших функций $$$f_{1}, \ldots, f_{n}$$$, которые определены во всех целых точках от $$$0$$$ до $$$10^{18}$$$ включительно, причем $$$f_i(0) = 0$$$ и $$$f_i(10^{18}) = L$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$. Также оказалось, что $$$L$$$ делится на $$$n$$$.

Она предложила Алесе сыграть в игру. Алеся может за один вопрос узнать у Тани значение какой-то одной функции в какой-то одной точке. Для того, чтобы выиграть, ей надо для всех $$$1 \leq i \leq n$$$ для $$$i$$$-й функции выбрать два целых числа $$$l_{i}$$$ и $$$r_{i}$$$ ($$$0 \leq l_{i} \leq r_{i} \leq 10^{18}$$$), что $$$f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}$$$, где $$$f_i(x)$$$ обозначает значение $$$i$$$-й функции в точке $$$x$$$ . Причем надо выбрать такие пары чисел, чтобы никакая пара отрезков $$$[l_i, r_i]$$$ не пересекалась (но могут касаться).

К сожалению, Таня не разрешает Алесе задать более $$$2 \cdot 10^{5}$$$ вопросов. Помогите Алесе выиграть!

Можно показать, что всегда можно выбрать такие $$$[l_i, r_i]$$$, которые удовлетворяют описанным выше условиям.

Гарантируется, что Таня не изменяет функции в процессе игры, то есть интерактор не адаптивный.

Входные данные

В первой строке находятся два числа $$$n$$$ и $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 10^{18}$$$, $$$L$$$ делится на $$$n$$$)  — число функций и их значение в точке $$$10^{18}$$$.

Выходные данные

Когда вы найдете нужные $$$l_i, r_i$$$, выведите $$$"!"$$$ и в следующих $$$n$$$ строках по паре чисел, в $$$i$$$-й из них — $$$l_i$$$ и $$$r_i$$$.

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

Чтобы узнать значение $$$f_i(x)$$$, в одной строке через пробел выведите символ «?», а затем два целых числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{18}$$$). Не забудьте сделать операцию 'flush', чтобы получить ответ.

В ответ на это считайте целое число, равное значению $$$i$$$-й функции в точке $$$x$$$.

Вы можете задать не более $$$2 \cdot 10^5$$$ вопросов.

Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода числа или ответа и перевода строки можно сделать:

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

Взломы:

Для взлома можно использовать только тесты с $$$1 \leq L \leq 2000$$$, для этого задайте тест в следующем формате.

В первой строке должны находиться два целых числа $$$n$$$ и $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 2000$$$, $$$L$$$ делится на $$$n$$$)  — число функций и их значение в $$$10^{18}$$$.

В каждой из следующих $$$n$$$ строк должны быть выведены $$$L$$$ чисел $$$l_1$$$, $$$l_2$$$, ... , $$$l_L$$$ ($$$0 \leq l_j < 10^{18}$$$ для всех $$$1 \leq j \leq L$$$ и $$$l_j < l_{j+1}$$$ для всех $$$1 < j \leq L$$$), в $$$i$$$-й строке $$$l_j$$$ значит что $$$f_i(l_j) < f_i(l_j + 1)$$$.

Пример
Входные данные
5 5
? 1 0
? 1 1
? 2 1
? 2 2
? 3 2
? 3 3
? 4 3
? 4 4
? 5 4
? 5 5
!
0 1
1 2
2 3
3 4
4 5
Выходные данные
0
1
1
2
2
3
3
4
4
4
5
Примечание

В примере у Пети $$$5$$$ одинаковых функций, что $$$f(0) = 0$$$, $$$f(1) = 1$$$, $$$f(2) = 2$$$, $$$f(3) = 3$$$, $$$f(4) = 4$$$, во всех остальных точках значение равно $$$5$$$.

Вася должен выбрать по два целых числа для каждой функции, что разность значений в этих точках, не менее $$$\frac{L}{n}$$$ (что равно $$$1$$$ в данном случае), и длина пересечения всех пар отрезков, образованных на этих числах, была нулевой.

Один из возможных способов  — это выбрать пары чисел $$$[0$$$, $$$1]$$$, $$$[1$$$, $$$2]$$$, $$$[2$$$, $$$3]$$$, $$$[3$$$, $$$4]$$$ и $$$[4$$$, $$$5]$$$ для функций $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$ соответственно.