Problem Statement

N students are about to go to school. Student i belongs to Class C_i.
After leaving home, each student will head to school while repeatedly joining up with a group of other students. Once students join up with each other, they will not separate.
You will be given Q queries that should be processed in order. There are two kinds of queries, in the following formats, that mean the following:

• 1 a b: The group containing Student a and the group containing Student b merges. (If they are already in the same group, nothing happens.)
• 2 x y: You are asked to find the number of students belonging to Class y who are already in the same group as Student x (including Student x) at the time of this query.

Input

Input is given from Standard Input in the following format:
N Q
$C_1 \ldots C_N$
Query_1
$\vdots$
Query_Q

Output

Print the answers to the queries in the format 2 x y, each in its own line, in order.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq C_i,a,b,x,y \leq N$
• In a query in the format $1 a b, a \neq b$.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2
0

At the time of the 3-rd query, Student 1 has joined up with Student 2 and 5. Among these three students, two belong to Class 1.
At the time of the 5-th query, Student 3 has joined up with Student 4. Among these two students, none belongs to Class 4.

Sample Input 2

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

Sample Output 2

3

There may be queries in the format 1 a b for students who already belong to the same group.

Sample Input 3

12 9
1 2 3 1 2 3 1 2 3 1 2 3
1 1 2
1 3 4
1 5 6
1 7 8
2 2 1
1 9 10
2 5 6
1 4 8
2 6 1

Sample Output 3

1
0
0

见题面 Input 部分

见题面 Output 部分