一排有 $n$ 个花盆，编号从 $1$ 到 $n$。你可以在这排花盆旁放置洒水器。 每个洒水器由其位置 $x$（$1$ 到 $n$ 之间的整数）和方向（向左或向右）来描述。

所有洒水器共享相同的洒水范围 $L$（一个非负整数）。

• 位于位置 $x$ 且向右指的洒水器可以浇灌索引在区间 $[x, x + L]$ 内的所有花盆。
• 位于位置 $x$ 且向左指的洒水器可以浇灌索引在区间 $[x - L, x]$ 内的所有花盆。

只有索引在 $1$ 到 $n$ 之间的花盆存在。

初始时，没有洒水器。你需要处理 $q$ 个以下两种类型的操作：

• 插入洒水器。格式为 “1 $d$ $x$” 的操作表示在位置 $x$ 插入一个新的洒水器。 如果 $d = 0$，洒水器向左指。 如果 $d = 1$，洒水器向右指。 同一个位置可以放置多个洒水器。操作按时间顺序给出，且没有删除操作。
• 区间查询。格式为 “2 $\ell$ $r$” 的操作提出以下问题： 考虑当前所有的洒水器集合。假设所有洒水器具有相同的范围 $L$。找到最小的整数 $L \ge 0$，使得区间 $[\ell, r]$ 内的每个花盆都至少被一个洒水器浇灌。注意，区间 $[\ell, r]$ 之外的洒水器也可以帮助浇灌 $[\ell, r]$ 内的花盆。如果没有整数 $L$ 能使 $[\ell, r]$ 内的所有花盆都被浇灌（无论 $L$ 有多大），你必须对该查询输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$），分别表示花盆的数量和操作的数量。

接下来的 $q$ 行，每行描述一个操作，必须按给出的顺序处理：

• “1 $d$ $x$”：在位置 $x$ 插入一个方向为 $d$ 的洒水器（$d \in \{0, 1\}$，$1 \le x \le n$）。这里，$d = 0$ 表示洒水器向左指，$d = 1$ 表示向右指。
• “2 $\ell$ $r$”：查询区间 $[\ell, r]$ 的最小范围 $L$（$1 \le \ell \le r \le n$）。

输出格式

对于每个格式为 “2 $\ell$ $r$” 的查询，输出单独一行，包含一个整数：

• 使得 $[\ell, r]$ 内的每个花盆都被浇灌的最小整数 $L \ge 0$，或者
• 如果不可能做到，输出 $-1$。

样例

输入样例 1

10 11
1 0 6
2 5 8
1 1 3
2 9 10
2 3 9
1 1 8
2 1 9
2 1 8
1 0 4
2 3 7
2 2 9

输出样例 1

-1
7
6
5
5
4
4