Gyeonggi Science High School, a famous landmark in Gyeonggi-do, has $N$ buildings, numbered from $1$ to $N$. Originally, there were roads connecting the buildings, but students from Seoul Science High School shouted "Split the GSHS!" and removed all the roads.

Enraged by this, Jaewoo tasks Woohyun with rebuilding the roads.

A road connects two distinct buildings bidirectionally. Two buildings are said to be connected if it is possible to travel from one building to the other through a sequence of roads. The distance between two buildings is the minimum number of roads that must be traversed to travel between them.

The building with the smallest index among all buildings connected to a certain building is called the 'central building' of that building. Note that all buildings connected to a certain building will share the same central building.

Jaewoo gives Woohyun $Q$ commands. The commands consist of the following two types:

• 1 A B: Build a road between building A and building B. It is guaranteed that before connecting the road, there is no building that can be reached from both A and B.
• 2 A B: If building A and building B are connected, output the index of the building that is closest to the central building of building A among all buildings on the shortest path between A and B (including A and B). If the two buildings are not connected, output 0.

You are Woohyun. Perform all of Jaewoo's commands.

Input

The first line contains an integer $N$, the number of buildings at Gyeonggi Science High School. The second line contains an integer $Q$, the number of commands Jaewoo gives to Woohyun. From the third line, $Q$ lines follow, each containing the type of query $T$ and two integers $X, Y$ separated by a space. Here,

• $A = X \oplus \texttt{last\_ans}$
• $B = Y \oplus \texttt{last\_ans}$

Perform the command T A B. last_ans is the value output by the most recent type 2 command, or 0 if no type 2 query has been performed yet.

Constraints: $2 \le N \le 10^5$ $2 \le Q \le 5 \times 10^5$

Output

On the $i$-th line, output the answer to the $i$-th type 2 query.

Examples

Input 1

7 15
1 1 7
2 1 7
1 7 2
2 2 7
1 0 7
2 7 5
1 6 5
2 6 5
2 0 2
1 2 5
2 4 7
2 2 4
1 4 0
2 4 1
2 3 2

Output 1

1
3
3
6
3
1
6
1
6