Назовем функцию хорошей, если ее область определения — целые числа, и если для любого \(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]\), которые удовлетворяют описанным выше условиям.
Гарантируется, что Таня не изменяет функции в процессе игры, то есть интерактор не адаптивный.
Выходные данные
Когда вы найдете нужные \(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\) одинаковых функций, что \(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\) соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
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
|