背景

小 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$ 的值。

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

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$。

子任务编号	特殊性质	分值
$1$	$n,q\le 10^4$	$10$
$2$	初始时序列 $a$ 单调不降
$3$	$k\le 100$
$4$	序列 $a$ 中 $0$ 的数量 $\le 100$
$5$	每次修改前 $a_x=-1$	$30$
$6$	无