8675: Cut

	The first line contains two integers $n,m$ (1≤n,m≤1051 \le n,m \le 10^51≤n,m≤105), denoting the number of trees and the number of operations.



	



	The second line contains $n$ integers a1,a2,…,ana_1,a_2, \ldots, a_na1,a2,…,an (1≤ai≤n1 \le a_i \le n1≤ai≤n), denoting the initial height of trees. It's guaranteed that a1,a2,…,ana_1,a_2, \ldots, a_na1,a2,…,an is a permutation of $1,2,\dots ,n$.



	

For the $i$-th line in the following $m$ lines, there are three integers oi,li,rio_i,l_i,r_ioi,li,ri (1≤oi≤3,1≤li≤ri≤n1 \le o_i \le 3, 1 \le l_i \le r_i \le n1≤oi≤3,1≤li≤ri≤n), denoting the type of the $i$-th operation and the range of the $i$-th operation.

For each operation in type 3, print an integer in a single line, denoting the answer of this operation.

3 3
1 3 2
3 1 3
1 2 3
3 1 3

2
3

In the first example, the initial height of trees is $[1,3,2]$. In the first operation, the maximum $k$ is $2$, since a1≢a3(mod2)a_1 \not \equiv a_3 \pmod 2a1≡a3(mod2) and a1≡a2(mod2)a_1 \equiv a_2 \pmod 2a1≡a2(mod2) (so $k$ cannot be $3$). After the second operation, the height of trees becomes $[1,2,3]$. In the third operation, the maximum $k$ is $3$, since a1≢a2(mod2)a_1 \not \equiv a_2 \pmod 2a1≡a2(mod2) and a2≢a3(mod2)a_2 \not \equiv a_3 \pmod 2a2≡a3(mod2).