$N$개의 원소를 갖는 수열 $P=\{0, 1, 2, \cdots, N-1\}$이 있다.

수열 $P$에 대해, 트리 $T_P$는 다음과 같이 정의된다.

• 총 $N$개의 정점을 가진다.
• $1$번 정점은 루트이며, $2 \le i \le N$에 대해 $i$번 정점의 부모는 $\max(P_i, 1)$번 정점이다.

아래의 쿼리를 수행하는 프로그램을 작성하라.

• $1 \ x \ a$: $P_x, P_{x+1}, \cdots, P_N$에서 각각 $a$를 뺀다.
• $2 \ x \ y$: 현재의 수열 $P$에 대해 정의된 트리 $T_P$에서, 두 정점 $x$와 $y$의 최소 공통 조상의 번호를 출력한다.

입력

첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. ($1 \le N, Q \le 100\,000$)

두 번째 줄부터 $Q$개의 줄에 걸쳐, $i+1$번째 줄에 $i$번째 쿼리를 의미하는 $3$개의 정수가 공백으로 구분되어 주어진다. ($1 \le x, y, a \le N$)

출력

2번 쿼리가 주어질 때마다, 답을 한 줄에 하나씩 출력한다.

2번 쿼리는 한 개 이상 주어짐이 보장된다.

Sample

Input

6 9
1 6 1
1 2 1
2 6 1
1 5 1
2 1 3
2 4 6
1 5 2
2 5 5
2 6 2

Output

1
1
2
5
1

Sample

Input

13 5
1 12 2
2 11 12
1 2 2
2 2 9
2 2 6

Output

9
1
1