给你一个含有 $n$ 个顶点的无向图。初始时，图中不包含任何边。

你需要对这个图执行两种类型的操作：

1. 在顶点 $u_i$ 和 $v_i$ 之间添加一条边。保证在此操作之前图中不存在该边，且执行该操作后图仍然是一个森林。
2. 输出满足顶点 $u_i$ 与 $w$ 之间的距离等于 $k_i$ 的顶点 $w$ 的数量。这里的距离是指连接 $u_i$ 和 $w$ 的简单路径上的边数。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 100\,000$，$1 \le q \le 200\,000$），分别表示顶点数和操作数。

接下来的 $q$ 行，每行包含三个整数 $t_i, a_i, b_i$（$1 \le t_i \le 2$，$0 \le a_i, b_i \le n - 1$），表示操作类型和描述该操作的两个数。

设 $last$ 为上一次类型 2 操作的答案，如果此前还没有进行过类型 2 操作，则 $last = 0$。

• 如果 $t_i = 1$，你需要在顶点 $u_i$ 和 $v_i$ 之间添加一条边，其中 $u_i = ((a_i + last) \bmod n) + 1$ 且 $v_i = ((b_i + last) \bmod n) + 1$。
• 如果 $t_i = 2$，你需要计算满足顶点 $u_i$ 与 $w$ 之间的距离为 $k_i$ 的顶点 $w$ 的数量，其中 $u_i = ((a_i + last) \bmod n) + 1$ 且 $k_i = (b_i + last) \bmod n$。

输出格式

对每个类型 2 的操作，在单独的一行中输出答案。

样例

输入 1

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

输出 1

2
3

说明

在样例中，实际执行的操作如下：

1. 在 1 和 2 之间添加一条边。
2. 在 3 和 4 之间添加一条边。
3. 在 3 和 5 之间添加一条边。
4. 寻找满足 3 与 $w$ 之间距离等于 1 的顶点 $w$ 的数量。存在两个这样的顶点：4 和 5；$last$ 变为 2。
5. 在 3 和 6 之间添加一条边。
6. 在 2 和 3 之间添加一条边。
7. 寻找满足 2 与 $w$ 之间距离等于 2 的顶点 $w$ 的数量。存在三个这样的顶点：4，5 和 6；$last$ 变为 3。