CF1179E.Alesya and Discrete Math

We call a function good if its domain of definition is some set of integers and if in case it's defined in $x$ and $x-1$, $f(x) = f(x-1) + 1$ or $f(x) = f(x-1)$.

Tanya has found $n$ good functions $f_{1}, \ldots, f_{n}$, which are defined on all integers from $0$ to $10^{18}$ and $f_i(0) = 0$ and $f_i(10^{18}) = L$ for all $i$ from $1$ to $n$. It's an notorious coincidence that $n$ is a divisor of $L$.

She suggests Alesya a game. Using one question Alesya can ask Tanya a value of any single function in any single point. To win Alesya must choose integers $l_{i}$ and $r_{i}$ ($0 \leq l_{i} \leq r_{i} \leq 10^{18}$), such that $f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}$ (here $f_i(x)$ means the value of $i$-th function at point $x$) for all $i$ such that $1 \leq i \leq n$ so that for any pair of two functions their segments $[l_i, r_i]$ don't intersect (but may have one common point).

Unfortunately, Tanya doesn't allow to make more than $2 \cdot 10^{5}$ questions. Help Alesya to win!

It can be proved that it's always possible to choose $[l_i, r_i]$ which satisfy the conditions described above.

It's guaranteed, that Tanya doesn't change functions during the game, i.e. interactor is not adaptive

我们称一个函数是“好”的，如果它的定义域是某个整数集合，且当它在 $x$ 和 $x-1$ 处均有定义时，满足 $f(x) = f(x-1) + 1$ 或 $f(x) = f(x-1)$。

塔尼娅找到了 $n$ 个“好”函数 $f_{1}, \ldots, f_{n}$，它们均在从 $0$ 到 $10^{18}$ 的所有整数上定义，且对所有 $i\in[1,n]$ 均有 $f_i(0) = 0$ 以及 $f_i(10^{18}) = L$。一个众所周知的巧合是：$n$ 整除 $L$。

她向阿列西娅提议一个游戏。阿列西娅每次提问可向塔尼娅询问任意一个函数在任意一个点上的取值。为赢得游戏，阿列西娅必须为每个 $i$（$1 \le i \le n$）选择整数 $l_{i}$ 和 $r_{i}$（满足 $0 \leq l_{i} \leq r_{i} \leq 10^{18}$），使得对所有 $i$ 都有 $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]$。

保证塔尼娅在游戏过程中不会更改函数，即交互器是非自适应的。

The first line contains two integers $n$ and $L$ ($1 \leq n \leq 1000$, $1 \leq L \leq 10^{18}$, $n$ is a divisor of $L$) — number of functions and their value in $10^{18}$.

第一行包含两个整数 $n$ 和 $L$（$1 \leq n \leq 1000$，$1 \leq L \leq 10^{18}$，且 $n$ 是 $L$ 的约数）—— 分别表示函数的个数及其在 $10^{18}$ 处的取值。

When you've found needed $l_i, r_i$, print $"!"$ without quotes on a separate line and then $n$ lines, $i$-th from them should contain two integers $l_i$, $r_i$ divided by space.

当找到所需的 $l_i, r_i$ 后，在单独一行输出不带引号的 "!"，然后输出 $n$ 行，其中第 $i$ 行应包含两个由空格分隔的整数 $l_i$ 和 $r_i$。

In the example Tanya has $5$ same functions where $f(0) = 0$, $f(1) = 1$, $f(2) = 2$, $f(3) = 3$, $f(4) = 4$ and all remaining points have value $5$.

Alesya must choose two integers for all functions so that difference of values of a function in its points is not less than $\frac{L}{n}$ (what is $1$ here) and length of intersection of segments is zero.

One possible way is to choose pairs $[0$, $1]$, $[1$, $2]$, $[2$, $3]$, $[3$, $4]$ and $[4$, $5]$ for functions $1$, $2$, $3$, $4$ and $5$ respectively.

在该示例中，塔尼娅有 $5$ 个相同的函数，满足 $f(0) = 0$、$f(1) = 1$、$f(2) = 2$、$f(3) = 3$、$f(4) = 4$，其余所有点的函数值均为 $5$。

阿列西娅必须为每个函数选定两个整数，使得该函数在其所选两点处的函数值之差不小于 $\frac{L}{n}$（本题中该值为 $1$），且所选区间段的交集长度为零。

一种可行方案是：分别为第 $1$、$2$、$3$、$4$、$5$ 个函数选择区间对 $[0, 1]$、$[1, 2]$、$[2, 3]$、$[3, 4]$ 和 $[4, 5]$。