Cho dãy $P = \{0, 1, 2, \cdots, N-1\}$ gồm $N$ phần tử.

Với dãy $P$, cây $T_P$ được định nghĩa như sau:

• Có tổng cộng $N$ đỉnh.
• Đỉnh $1$ là gốc, và với mọi $2 \le i \le N$, cha của đỉnh $i$ là đỉnh $\max(P_i, 1)$.

Hãy viết chương trình thực hiện các truy vấn sau:

• $1 \ x \ a$: Từ $P_x, P_{x+1}, \cdots, P_N$, mỗi phần tử trừ đi $a$.
• $2 \ x \ y$: Trong cây $T_P$ được định nghĩa từ dãy $P$ hiện tại, in ra số hiệu của tổ tiên chung nhỏ nhất của hai đỉnh $x$ và $y$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$, $Q$ cách nhau bởi dấu cách. ($1 \le N, Q \le 100\,000$)

$Q$ dòng tiếp theo, dòng thứ $i+1$ chứa ba số nguyên cách nhau bởi dấu cách thể hiện truy vấn thứ $i$. ($1 \le x, y, a \le N$)

Dữ liệu ra

Mỗi khi có truy vấn loại 2, in ra kết quả trên một dòng riêng biệt.

Đảm bảo có ít nhất một truy vấn loại 2.

Ví dụ

Đầu vào 1

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

Đầu ra 1

1
1
2
5
1

Đầu vào 2

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

Đầu ra 2

9
1
1