作为一名高级指挥官，你必须与你的士兵一起坚守阵地。你已经构建了一条由 $N$ 个战壕组成的防线，编号从 $1$ 到 $N$，每个战壕最初都是空的。士兵们正在等待你的命令，每名士兵都有一个偏好的射击高度。

随着战斗的进行，可能会发生以下两类事件：

• 一名偏好射击高度为 $h$ 的士兵被派往一个空战壕驻守。
• 发现了一名高度为 $H$ 的敌人，只有驻守在编号为 $L$ 到 $R$ 之间战壕的士兵可以射击该敌人。为了提高命中率从而节省子弹，必须选择一名偏好射击高度与敌人高度最接近的士兵来射击。你需要求出所选士兵的偏好射击高度与敌人高度之差的绝对值。

你的情报副官预测在战斗中会发生 $M$ 次事件。为了更好地为战斗做准备，你需要编写一个程序来模拟这些事件并研究结果。

输入格式

输入包含多组数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示数据组数。

对于每组数据，第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 5 \cdot 10^5, 1 \le M \le 10^6$)，分别表示战壕数量和事件数量。

接下来的 $M$ 行，每行包含三个或四个整数，按时间顺序描述事件。第 $i$ 行 ($1 \le i \le M$) 描述第 $i$ 个事件。每行的第一个整数表示 $type$ ($type \in \{0, 1\}$)。如果 $type = 0$，后面会跟两个整数 $x, h$，表示一名偏好射击高度为 $h$ ($1 \le h \le 10^9$) 的士兵现在驻守在空战壕 $x$ ($1 \le x \le N$) 中。如果 $type = 1$，后面会跟三个整数 $L, R, H$，表示发现了一名高度为 $H$ ($1 \le H \le 10^9$) 的敌人，只有编号在 $L$ 到 $R$ ($1 \le L \le R \le N$) 之间的战壕中的士兵可以射击该敌人。

保证所有数据中 $N$ 的总和不超过 $5 \cdot 10^5$，且所有数据中 $M$ 的总和不超过 $10^6$。

输出格式

对于每个 $type = 1$ 的事件，单行输出一个整数，表示所选士兵的偏好射击高度与敌人高度之差的绝对值。如果编号在 $L$ 到 $R$ 之间的战壕中没有驻守任何士兵，则输出 $-1$。

样例

样例输入 1

1
3 5
1 1 3 2
0 1 1
0 3 3
1 1 2 2
1 2 3 2

样例输出 1

-1
1
1

Figure 1. Illustration of a trench system