实验室中有 $n$ 种试剂，编号分别为 $1,2,\cdots,n$，其中试剂 $i$ 的危险程度为 $i$。你正在进行化学实验，但现在，你不知道任何化学反应。接下来发生了 $q$ 个事件，每个事件为以下两种形式之一：

1 x y：你知道了如何通过化学反应使试剂 $x$ 与试剂 $y$ 互相转化。

2 x y：你现在只有试剂 $x$，求有多少试剂 $x^\prime$ 满足，你可以用试剂 $x$ 通过若干反应生成试剂 $x^\prime$，且反应过程中产生的所有试剂的危险程度均不超过 $y$。

由于你很急切地想要知道实验结果，所以询问将强制在线。

输入格式

第一行：三个整数 $t,n,q$。

接下来 $q$ 行：每行三个整数 $op,x_0,y_0$，表示一个事件 op x y，其中 $x=(x_0-1+t\times lastans)\bmod n+1$，$y=(y_0-1+t\times lastans)\bmod n+1$，$lastans$ 为上一次询问的答案（不存在则为 $0$）。

输出格式

对于每个 $op=2$ 的事件，输出一行一个整数，表示答案。

样例一

input

0 5 15
1 3 4
2 1 4
1 5 1
2 5 5
1 3 5
1 4 3
1 2 1
2 2 4
2 4 4
2 4 5
2 2 2
2 1 3
1 1 5
1 3 1
2 3 4

output

1
2
2
2
5
2
2
4

数据范围

对于所有数据，满足 $t\in\{0,1\}$，$1\le n,q\le 5\times 10^5$，$op\in\{1,2\}$，$1\le x_0,y_0\le n$。当 $op=1$ 时，$x\neq y$；当 $op=2$ 时，$x\le y$。