You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

最近，神犇在未来交通工具展览会上购买了一辆「$m$ 循环车」。这种交通工具的特点是：车门每行驶 $m$ 米才能开启一次。

展会结束后他准备回家，然而插入钥匙后，车内的一切突然扭曲了起来 …… 接着他发现自己到了一个奇怪的地方。这时空中传来一个声音：

哈哈哈 …… 我请你们来这里，就是为了考验一下你们的水平。这个世界是一张无向图，有 $n$ 个点，暂时还没有边。等一会我把边加上之后，每条边会有一个长度，第 $i$ 条边长 $w_i$ 米。
你们的车一旦驶上一条边，就必须开到这条边的尽头，中途没有回转的余地。

现在你们将要接受 $q$ 次考验。考验有两种：

1. 告诉你们三个整数 $u,v,w$ 表示我在 $u$ 和 $v$ 之间加了一条长 $w$ 米的边；
2. 告诉你们五个整数 $u,v,x,b,c \ (u\neq v)$，其中 $x,b$ 描述了一个伪随机数生成器，它第一次的返回值 $f_1=x\bmod m$，以后每次的返回值 $f_{i+1}=(f_i+b)\bmod m$。你们要回答，对于 $i=1,2,\ldots,c$，有多少个 $i$ 满足：如果你的车离最近一次能够开门的机会还有 $f_i$ 米，那么存在一条路径使你能从 $u$ 出发到 $v$ 下车。

除非你们的回答全部正确且快速，否则我是不会放你们离开这里的 …… 哈哈哈 ……

按照套路，神犇自然是一眼秒掉了这个问题。不过为了不让黑恶势力白白出场，他想请你也解决一下这个问题。

简略题意：一个带边权无向图，有两种操作：加边以及询问在 $x,x+b,...,x+(c-1)b$ 这些数中，有多少数存在一条从 $u$ 到 $v$ 的路径长度与之模 $m$ 同余（可以不是简单路径）。

Format

Input

第一行三个整数 $n,m,q$。
接下来 $q$ 行，每行描述一次考验，内容如下：

• $\texttt{1 u v w}$ 表示 $u$ 和 $v$ 之间加了一条长 $w$ 米的边；
• $\texttt{2 u v x b c}$ 表示询问对于 $i=1,2,\ldots,c$，有多少个 $i$ 满足：如果你的车离最近一次能够开门的机会还有 $f_i$ 米，那么存在一条路径使你能从 $u$ 出发到 $v$ 下车。

Output

对于每个第二种考验，输出一行一个整数表示答案。

Samples

6 6 10
1 1 2 3
2 1 2 0 0 1
1 2 3 3
1 1 3 3
2 1 2 0 0 1
1 4 5 6
1 5 6 4
2 4 6 2 0 1
1 3 4 6
2 1 6 0 1 6

0
1
1
6

Limitation

对于 $100\%$ 的数据，$1\leq n,q\leq 10^6,1< m\leq 10^9,1\leq w\leq m,0\leq x,b< m,1\leq c\leq 10^9$。操作 2 中保证 $u\neq v$。

当车离最近一次能够开门的机会还有 $r$ 米时，「存在一条路径使你能从 $u$ 出发到 $v$ 下车」的意思是 $u$ 和 $v$ 之间存在一条路径（可以不是简单路径）长度模 $m$ 为 $r$。

注意，路径可以不是简单路径。

出题人的关怀：由于输入规模较大，建议使用读入优化；请相信 HFOJ 测评机的速度。