Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4089
Little Sub and Isomorphism Sequences

Time Limit: 3 Seconds      Memory Limit: 65536 KB

Little Sub has a sequence $A_1,A_2,\dots,A_N$. Now he has a problem for you.

Two sequences $X_1, X_2, \dots, X_u$ of length $u$ and $Y_1, Y_2, \dots, Y_v$ of length $v$ are considered isomorphic when they meet all the following two conditions:

  1. $u = v$;
  2. Define $\text{occ}(S,k)$ as the number of times integer $k$ occur in sequence $S$. For each integer $k$ in $[1, 10^9]$, $\text{occ}(X,k)=\text{occ}(Y,k)$ always holds.

Now we have $M$ operations for $A$. and there are two kinds of operations:

  • 1 x y: Change $A_x$ to $y$ ($1 \le x \le N$, $1 \le y \le 10^9$);
  • 2: Query for the greatest $k$ ($1 \leq k \leq N-1$) that there exist two integers $i$ and $j$ ($1 \leq i \lt j \leq N-k+1$) and $A_i, A_{i+1}, \dots, A_{i+k-1}$ is isomorphic with $A_j, A_{j+1}, \dots, A_{j+k-1}$. Specially, if there is no such $k$, please output "-1" (without quotes) instead.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 5$), indicating the number of test cases. For each test case:

The first line ontains two integers $N,M \ (1 \le N \le 10^5, 1 \le M \le 10^5)$.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).

In the following $M$ lines, each line contains one operation. The format is described above.

Output

For each operation 2, output one line containing the answer.

Sample Input

1
3 5
1 2 3
2
1 3 2
2
1 1 2
2

Sample Output

-1
1
2

Author: LI, Yankui
Source: ZOJ Monthly, January 2019
Submit    Status