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.

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.

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.