Có một khu rừng (forest) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$. Ban đầu rừng không có cạnh nào.

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

• 1 u v: Thêm một cạnh nối hai đỉnh $u$ và $v$ vào rừng. Đảm bảo rằng trước khi truy vấn này được gọi, không có đường đi nào giữa $u$ và $v$ trong rừng.
• 2 u k: Định nghĩa $dist(u, v)$ là độ dài đường đi ngắn nhất giữa hai đỉnh $u$ và $v$. Nếu hai đỉnh không được kết nối thì giá trị là $\infty$. Trả về số lượng đỉnh $v$ thỏa mãn $dist(u, v) = k$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N \le 100\,000, 1 \le Q \le 200\,000$).

$Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $t_i, a_i, b_i$ là thông tin của truy vấn ($1 \le t_i \le 2, 0 \le a_i, b_i < n$).

Xét thêm biến $last$. Biến này được khởi tạo bằng $0$.

• Khi $t_i = 1$, các tham số của truy vấn $u_i, v_i$ được định nghĩa như sau:
  $u_i = ((a_i + last) \bmod n) + 1$, $v_i = ((b_i + last) \bmod n) + 1$
• Khi $t_i = 2$, các tham số của truy vấn $u_i, k_i$ được định nghĩa như sau:
  $u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$
  Sau khi tính kết quả của truy vấn này, cập nhật $last$ thành kết quả đó.

Dữ liệu ra

In ra kết quả của các truy vấn dạng $t_i = 2$, mỗi kết quả trên một dòng.

Ví dụ

Đầu vào

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

Đầu ra

1
2
1