实验室中有 $ 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 $。