题意：一个带边权无向图，加边以及询问在 x,x+b,...,x+(c−1)bx,x+b,...,x+(c-1)bx,x+b,...,x+(c−1)b 这些数中，有多少存在一条与之模 m 同余的从 u 到 v 的路径（可以不是简单路径）。
考场上读错题系列，以为边是有向的，然后就完全不可做了对不对……
由于是无向边，而且路径可以不是简单路径，那就意味着我们可以在联通块内随便绕圈。那就变成了一个数是否能在模m意义下被各圈大小线性表出的问题，加上这些数是用等差数列的形式给出，也就是同余方程，这就是一个同余方程组了嘛，然后拓欧解解就行了。
#include<cstdio>
#include<algorithm>
#define MN 1100000
#define ll int
using namespace std;
int read_p,read_ca,read_f;
inline int read(){
read_p=;read_ca=getchar();read_f=;
while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p*read_f;
}
int n,m,Q,f[MN],opt,x,y,z,q,c,a,b;
ll d[MN],g[MN];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int gf(int x){
if (x==f[x]) return x;
int w=gf(f[x]);
(d[x]+=d[f[x]])%=m;
return f[x]=w;
}
int exgcd(int x,int y,int &a,int &b){
if (y){
int t=exgcd(y,x%y,b,a);
b-=x/y*a;
return t;
}else return a=,b=,x;
}
int main(){
n=read();m=read();Q=read();
for (int i=;i<=n;i++) f[i]=i,d[i]=,g[i]=m;
while (Q--){
opt=read();
if (opt==){
x=read(),y=read(),z=read();
int X=gf(x),Y=gf(y);
if (X==Y) g[X]=gcd(g[X],((z+d[x])%m+d[y])%m);else{
f[X]=y;(d[X]=d[x]+z)%=m;
g[Y]=gcd(g[Y],gcd(z*%m,g[X]));
}
}else{
x=read();y=read();q=read();c=read();z=read();
int X;
if ((X=gf(x))!=gf(y)) puts("");else{
q=(d[x]+d[y]-q)%m+m;q%=g[X];
if (q%(x=exgcd(c,g[X],a,b))){puts("");continue;}
y=g[X]/gcd(g[X],c);
a=1LL*q/x*a%y;if (a<) a+=y;z--;
printf("%d\n",(z-a+y)/y);
}
}
}
}