题目描述

有 $n$ 个点，编号从 $1$ 到 $n$。初始时每个点都没有被标记。

接下来有 $q$ 次操作，操作分为如下两种类型：

• $\mathtt{1\ x}$：对编号为 $x$ 的点进行标记；
• $\mathtt{2\ l\ r\ k}$：查询从第 $l$ 个点开始到第 $r$ 个点结束（包含第 $l$ 和第 $r$ 个点）范围内从左往右第 $k$ 个被标记的点的编号。

对于每次查询操作，输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $q$，以一个空格分隔（$1 \le n,q \le 5 \cdot 10^5$）。

接下来 $q$ 行，每行包含一次操作，形如：

• $\mathtt{1\ x}$（$1 \le x \le n$ 且每次标记的都是之前从未标记过的点），或
• $\mathtt{2\ l\ r\ k}$（ $1 \le l \le r \le n$ 且第 $l$ 到第 $k$ 个点范围内至少有 $k$ 个被标记的数）

输出格式

对于每次查询操作，输出一行，包含一个整数，表示第 $l$ 个点开始到第 $r$ 个点范围内从左往右数第 $k$ 个被标记的点的编号。

样例

10 7
1 3
1 6
1 8
2 1 7 2
1 4
2 1 7 2
2 3 10 4

6
4
8

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,q \le 50$
• 对于 $60\%$ 的数据，$n,q \le 5000$
• 对于 $100\%$ 的数据，$n,q \le 5 \cdot 10^5$