$N$ 个顶点组成的森林。顶点编号为 $1$ 到 $N$。初始森林中没有边。

编写一个程序执行以下查询：

• 1 u v: 在森林中添加一条连接顶点 $u$ 和 $v$ 的边。保证在此查询被调用之前，森林中不存在连接 $u$ 和 $v$ 的路径。
• 2 u k: 定义 $dist(u, v)$ 为两个顶点 $u, v$ 之间最短路径的长度。如果两个顶点不连通，则该值为 $\infty$。返回满足 $dist(u, v) = k$ 的顶点 $v$ 的个数。

输入格式

第一行包含两个整数 $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 < n$)

考虑一个额外的变量 $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, k_i$ 定义如下：$u_i = ((a_i + last) \bmod n) + 1$, $k_i = ((b_i + last) \bmod n)$。计算完此查询的答案后，将 $last$ 更新为该查询的答案。

输出格式

对于每个 $t_i = 2$ 的查询，输出其答案，每行一个。

样例

输入

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

输出

1
2
1