Background

Little C is trying to clear a hidden song, and his good friend Little A just achieved a Pure Memory.

Little C also wants to become a PM master like Little A, so he needs you to solve a problem regarding PM (Prefix Mex).

Description

Note: The definition of $\operatorname{mex}$ in this problem differs from the standard definition.

For a multiset $S$, $\operatorname{mex}(S)$ is defined as the smallest positive integer $x$ such that $x \notin S$.

Given an array $a_1, a_2, \dots, a_n$, where it is guaranteed that $-1 \le a_i \le n$, the array $b_1, b_2, \dots, b_n$ is generated as follows:

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

You are given an array $a_1, a_2, \dots, a_n$ of length $n$, guaranteed that initially $a_i \in \{-1, 0\}$ and the array $a$ is not all zeros.

There are $q$ operations. Each operation provides three integers $x, k, y$, where $1 \le x, y \le n$, $a_x \ne 0$, $-1 \le k \le n$, and $k \ne 0$. This means you first modify $a_x$ to $k$, and then you need to find the value of $b_y$ in the array $b$ generated by the current array $a$.

Note: Any $a_i$ that is $0$ will never be modified, and any $a_i$ that is not $0$ will never be modified to $0$.

Input

The first line contains two positive integers $n, q$.

The second line contains $n$ integers describing $a_1, a_2, \dots, a_n$, guaranteed that initially $a_i \in \{-1, 0\}$ and the array $a$ is not all zeros.

The next $q$ lines each contain 3 integers $x, k, y$, describing an operation.

Output

Output $q$ lines, where the $i$-th line contains an integer representing the value of $b_y$ in the array $b$ generated after the $i$-th modification.

Examples

Input 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

Output 1

6
1
3
1
2
3
1
4
3
5

Input 2

See the provided files, which satisfy the constraints of Subtask 1.

Constraints

For $100\%$ of the data, $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$, and $k \ne 0$. The array $a$ is guaranteed not to be all zeros.