Problem K
Team Up!

Life of the undercity can be boring sometimes. There are $N$ children in the undercity, and they have decided to play a new game — Team Up! Each player is on a team, and each turn, a team is selected uniformly at random. Two players, $i$ and $j$, can use their team’s turn to “team up” on player $k$, if and only if $i < k < j$. After this, player $k$ joins $i$ and $j$’s team. A team may choose to pass (do nothing) on any given turn.

Figure 1: Players 2 and 6 team up on player 5.

A team with one player remaining is considered eliminated, as that team can never make a turn again. When only one team is not eliminated, that team is the winner. A team is the effective winner if the probability that they will win, with perfect play, is $1$.

Figure 2: Team 3 has won.

Figure 3: Team 3 is the effective winner; no amount of random luck or perfect play from opposing teams will prevent team 3 from eventually winning.

Note that some games may not have a winner. In the following example, neither team can ever win, and the game ends in a draw:

Figure 4: Neither team can make any progress.

The children want to keep track of who is winning. You are given $Q$ queries, of the form:

• 1 t i: Player i joins team t. This turn may not necessarily be valid by the rules of the game (children of the undercity don’t always play fair); there are no restrictions on when a player might change teams.

• 2 t: Output the number of consecutive turns a team needs to have effectively won, assuming the children play perfectly and follow all rules, or $-1$ if they cannot win, even with unlimited consecutive turns.

Here, a team having $k$ consecutive turns means that team is selected and gets to make a move for the next $k$ consecutive turns. Can you help the children keep track of who is winning?

Input

The first line contains two integers, $N$ ($2 \leq N \leq 3 \cdot 10^5$) and $Q$ ($1 \leq Q \leq 3 \cdot 10^5$).
The second line contains $N$ integers, $a_1, a_2, \dots , a_N$, where $1 \leq a_i \leq N$ denotes the initial team of the $i$-th player.
Each of the following $Q$ lines contains one query in one of the following formats:

• 1 t i: Here, $t$ is a team identifier ($1 \le t \le N$) and $i$ is a player index ($1 \leq i \leq N$).

• 2 t: Here, $t$ is a team identifier ($1 \le t \le N$).

It is guaranteed that there is at least one query of the second type.

Output

For each query of the form 2 t, output a single line containing one integer — the number of consecutive turns a team needs to have effectively won, or $-1$ if the team cannot win even with unlimited consecutive turns.

4 5
1 2 1 2
2 1
2 2
1 1 2
2 1
2 2

1
1
0
-1

5 2
1 2 1 2 1
2 1
2 2

0
-1

4 2
1 1 2 2
2 1
2 2

-1 
-1

6 8
2 3 2 1 3 1
2 3
2 1
1 3 3
2 3
2 1
1 1 5
2 3
2 1

2
-1
1
-1
-1 
-1