경기도의 명소 경기과학고에는 $N$개의 건물이 있으며, 각 건물은 $1$부터 $N$까지 번호가 매겨져 있다. 원래는 건물들 사이를 연결하는 도로가 존재했지만, 서울과학고 학생들이 "Split the GSHS!"를 외치며 모든 도로를 제거해 버렸다.

이를 보고 분노한 재우는 우현이를 시켜 도로를 다시 건설하려 한다.

도로는 서로 다른 두 건물을 양방향으로 연결한다. 한 건물에서 도로 몇 개를 통해 다른 건물까지 갈 수 있다면, 두 건물이 연결되어 있다고 한다. 이때 두 건물 사이의 거리는 두 건물 사이를 이동하기 위해 지나야 하는 도로 수의 최솟값이다.

어떤 건물과 연결되어 있는 모든 건물 중 번호가 가장 작은 건물을 그 건물의 '중심 건물'이라고 하자. 이때, 어떤 건물과 연결되어 있는 모든 건물의 중심 건물은 같게 된다.

재우는 우현이에게 Q번의 명령을 내린다. 명령은 다음 두 가지 유형으로 이루어진다.

• 1 A B: 건물 A와 B 사이에 도로를 연결한다. 도로를 연결하기 전, A와 B 모두로 이동할 수 있는 건물이 존재하지 않음이 보장된다.
• 2 A B: A번 건물과 B번 건물이 연결되어 있다면, 두 건물 사이를 최단거리로 이동하기 위해 지나야 하는 건물 (A와 B를 포함) 중 A번 건물의 중심 건물과 가장 가까운 건물의 번호를 출력한다. 만약 두 건물이 연결되어 있지 않다면 0을 출력한다.

여러분은 우현이다. 재우의 명령들을 모두 수행해라.

1. $2 \le N, Q \le 5*10^3$
2. $2 \le N \le 5*10^3$
3. 추가 제약 조건 없음

Input

첫째 줄에 경기과학고등학교의 건물의 수를 나타내는 정수 $N$이 주어진다. 둘째 줄에는 재우가 우현이에게 내리는 명령의 개수 $Q$가 주어진다. 셋째 줄부터 $Q$개의 줄에는 쿼리의 종류를 나타내는 $T$와 두 정수 $X, Y$가 공백을 사이에 두고 주어진다. 이 때,

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

에 대해 명령 T A B를 수행하여라. last_ans는 가장 마지막으로 수행한 2번 명령에서 출력한 값이며, 만약 2번 쿼리를 이전까지 한 번도 수행하지 않았다면 0이다.

• $2 \le N \le 10^5$
• $2 \le Q \le 5*10^5$

Output

i번째 줄에는 i번째 2번 쿼리에 대한 정답을 출력한다.

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

Note

대충 1번 예제 주고 그림을 많이 준다.