You have arrived at an unknown archipelago, where islands are numbered from $1$ to $n$.

You can travel between islands using one-way portals. Due to local customs, there are only two one-way portals on island $i$: one leading to island $i+1$ and one leading to island $a_i$.

Initially, you are on the island numbered $x$, and you wish to reach island $1$ to complete a task. However, you discover that these portals may not necessarily lead you to island $1$. For convenience, you wish to travel to the island with the smallest possible index that is reachable from your current location.

Due to the influence of space-time turbulence, the portals between islands may change.

You need to solve this problem as quickly as possible.

Input

The first line contains two integers $n$ and $m$, representing the number of islands and the number of events, respectively.

The second line contains $n$ integers, representing $a_1, \dots, a_n$.

The next $m$ lines each begin with an integer $type$ representing the type of event. If $type = 1$, it is followed by two integers $x$ and $y$, indicating that $a_x$ changes to $y$. If $type = 2$, it is followed by an integer $x$, representing the starting point of the query.

Output

For each query, output one line containing the answer.

Constraints

For all data, $n, m \le 10^5$, $1 \le a_i \le n$.

• Subtask 1 (20 points): $n, m \le 100$.
• Subtask 2 (20 points): $type = 2$.
• Subtask 3 (60 points): No special restrictions.

Examples

Input 1

4 3
4 1 4 3
2 4
1 3 2
2 4

Output 1

3
1