题目描述

维护一个长度为 $N$ 的数组 $a$，初始时所有元素均为 $0$。有 $M$ 次操作，每次操作为以下两种之一：

• 1 x v：将 $a_x$ 更新为 $\max(a_x, v)$。（即若 $v$ 大于当前位置的原值，则将其修改为 $v$，否则不变）
• 2 x：查询前缀最大值 $\max(a_1, a_2, \dots, a_x)$。

请你对每次查询操作输出相应的结果。

输入格式

第一行包含两个整数 $N, M$，分别表示数组长度和操作次数。
接下来 $M$ 行，每行表示一次操作，格式如下：

• 1 x v 表示第一种操作（$1 \le x \le N$，$v$ 为整数）；
• 2 x 表示第二种操作（$1 \le x \le N$）。

输出格式

对于每个 2 x 操作，输出一行一个整数，表示查询到的前缀最大值。

样例

5 6
1 2 5
2 3
1 1 3
2 3
1 2 7
2 3

5
5
7

样例解释

初始数组：[0, 0, 0, 0, 0]

1. 1 2 5：令 $a_2 = \max(0, 5) = 5$，数组变为 [0, 5, 0, 0, 0]。
2. 2 3：查询前三个元素的最大值，为 $\max(0, 5, 0) = 5$，输出 5。
3. 1 1 3：令 $a_1 = \max(0, 3) = 3$，数组变为 [3, 5, 0, 0, 0]。
4. 2 3：查询前三个元素的最大值，为 $\max(3, 5, 0) = 5$，输出 5。
5. 1 2 7：令 $a_2 = \max(5, 7) = 7$，数组变为 [3, 7, 0, 0, 0]。
6. 2 3：查询前三个元素的最大值，为 $\max(3, 7, 0) = 7$，输出 7。

数据范围与提示

• 对于 $30\%$ 的数据，$N, M \le 2000$；
• 对于 $100\%$ 的数据，$1 \le N, M \le 2 \times 10^5$，$1 \le x \le N$，$-10^9 \le v \le 10^9$。