题目背景

小 C 正在堆尸解隐藏曲的时候，他的好朋友小 A 随手就 Pure Memory 了。

小 C 也想成为像小 A 一样的 PM 大师，所以他需要你解决一个关于 PM（Prefix Mex）的问题。

题目描述

注意，本题对 $\operatorname{mex}$ 的定义与一般的定义不同。

对于可重集 $S$ 定义 $\operatorname{mex}(S)$ 表示最小的 正整数 $x$ 满足 $x \notin S$。

对于给定的数组 $a_1, a_2, \dots, a_n$，保证 $-1 \le a_i \le n$，使用以下的方式生成数组 $b_1, b_2, \dots, b_n$：

$$ b_i = \begin{cases} a_i & a_i \ne 0 \\ \operatorname{mex}(\{b_1, b_2, \dots, b_{i-1}\}) & a_i = 0 \end{cases} $$

现在给定长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，保证初始时 $a_i \in \{-1,0\}$ 且数组 $a$ 不全为 $0$。

给定 $q$ 次操作，每次操作给定三个整数 $x, k, y$，保证 $1 \le x, y \le n$，$a_x \ne 0$，$-1 \le k \le n$ 且 $k \ne 0$。表示先将 $a_x$ 修改为 $k$，然后你需要求出使用当前的数组 $a$ 所生成的数组 $b$ 中 $b_y$ 的值。

注意，任意时刻为 $0$ 的 $a_i$ 不会被修改，不为 $0$ 的 $a_i$ 不会被修改为 $0$。

输入格式

第一行两个正整数 $n, q$。

第二行 $n$ 个整数，描述 $a_1, a_2, \dots, a_n$，保证初始时 $a_i \in \{-1,0\}$ 且数组 $a$ 不全为 $0$。

接下来 $q$ 行，每行 3 个整数 $x, k, y$，描述一次操作。

输出格式

共 $q$ 行，第 $i$ 行输出一个整数表示使用第 $i$ 次修改操作后的数组 $a$ 所生成的数组 $b$ 中 $b_y$ 的值。

样例

输入样例 1

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

输出样例 1

6
1
3
1
2
3
1
4
3
5

样例 2

见下发文件，其满足子任务 1 的限制。

数据范围

对于 $100\%$ 的数据，保证 $1 \le n, q \le 10^6$，$a_i \in \{-1,0\}$，$1 \le x, y \le n$，$a_x \ne 0$，$-1 \le k \le n$ 且 $k \ne 0$。保证数组 $a$ 不全为 $0$。