小 M 的星系中有 $n$ 颗有人居住的星球。起初这些星球之间的距离过于遥远，一个人无法在有生之年到达另一个星球，移民往往是几代人接力完成，旅游、看望族裔更是无从谈起。
后来，五维生物为人们建立了空间翘曲轨道。穿越轨道的人会感觉自己瞬间便到达了目的地，但对于外界来说，时间已经发生了巨大的变化，可能过去了几千年，也可能倒退几千年。
形式化地讲，可以用 $3$ 个数描述一条轨道：$u, v, w$，表示这条轨道连接了星球 $u$ 和星球 $v$，若从 $u$ 穿过轨道到达 $v$，时间会改变 $w$；若从 $v$ 穿过轨道到达 $u$，时间会改变 $-w$。注意到 $w$ 可正可负，当时间改变为正时，表示会经过这么长时间；为负值时，表示会倒流这么长时间；为零则表示时间不会变化。
有了轨道以后，人们便可以实现到其他星球的短期旅行，但同时也催生了新的需求：希望在特定时间到达某个星球，以看到特定的人或看到特定的历史事件。为了达到这一需求，人们可以经过任意多条轨道，在穿越多个星球以后到达目的地。
形式化地讲，可以用 $3$ 个数描述一条需求：$u, v, w$，表示希望从星球 $u$ 出发，到达星球 $v$，与出发时间相比，中途的时间改变为 $w$ (注意这里的 $w$ 也可正可负)。
现在的问题是，给出轨道的建立过程和过程中所有的需求，问每条需求是否能得到满足。
具体地，你将依次得到 $m$ 条操作，每条操作为建立一条轨道或一条需求。若为一条需求，你需要回答只使用需求之前的所有轨道，"能" 还是 "不能" 完成这个需求。
第一行包含四个非负整数 $n, m, k, t$ ($1 \leq n \leq 10^5; 1 \leq m \leq 10^6; k, t \in \{0, 1, 2, 3\}$)，其中 $n, m$ 如前文所述，$k, t$ 为跟数据格式相关的参数。
接下来 $m$ 行，每行包含 $6$ 个非负整数 $p, \hat u, \hat v, w, x, y$ ($p \in \{0, 1\}; 1 \leq \hat u, \hat v \leq n; \left| w \right| \leq 10^{12}; 0 \leq x, y \leq 2^{30}$)。
其中 $p$ 表示操作的类型，$0$ 表示新建轨道，$1$ 表示一条需求，剩余 $3$ 个变量意义如前文所述。
注意 $u, v$ 是经过加密的。你需要维护一个变量 $mask$，初值为 $0$。每次询问时，令
$$ u = \left( \hat u + (x \mathbin{\&} mask) - 1 \right) \bmod n + 1; v = \left( \hat v + (y \mathbin{\&} mask) - 1 \right) \bmod n + 1$$
其中 $\&$ 代表按位与运算。
每次输出时，设你输出的答案为 result，则令 mask = (mask << 1 | result) & 0x3fffffff。
对于每条需求，你需要输出一行一个整数 $result$，如果能完成需求，则输出 $1$，如果不能完成需求，则输出 $0$。
由于旅行的轨迹是一条途径 (walk) (即可以经过重复边，定义戳这里)，且反着走一条边提供相反的权值。因此与 "异或" 的 [SimpleOJ282]防御阵 一样，如果 $u, v$ 连通，则 $u$ 到 $v$ 的所有途径的边权和，等于其中任意一条途径的边权和，加上若干个环的边权和的线性组合。
其中 "异或" 运算的线性组合可以用 (异或) 线性基来刻画，那 "加法" 运算的线性组合呢？
是的，$a_1, a_2, \cdots, a_n$ 对于加法运算的线性组合就是由 $d$ 生成的主理想，即由所有 $d$ 的整数倍数构成。其中 $d = \gcd \left( a_1, a_2, \cdots, a_n \right)$，可以使用 Bézout 定理证明。
如果这道题是离线的，那很好办。跟那道题的思路一样，先取出最终图的一个生成树 $T$ (如果不连通则取生成森林 $F$)，这样就得到了两点之间的连通性和其中一条途径的边权和 $w_0$ (树上前缀和)。然后维护出一个连通块中所有环的边权和的最大公约数 $d$，然后只需判断 $w - w_0$ 是不是 $d$ 的倍数即可。
那如果强制在线该怎么办呢？想想如何动态维护一张只有加边的距离关系图？
对！就是并查集！带权的并查集！
像这道题一样，用带权并查集维护当前图的一个生成森林 $F$ 的两点之间的距离，以及每个连通块中所有环的边权和的 gcd。
这些都是可以用带权并查集轻松维护的，具体过程这里就不细讲了，可以看上面那篇题解。
判定时也是类似地，如果 $u, v$ 不连通，显然无解。否则，在该连通块中得到 $w_0 = \mathrm{dist}(u, v)$ 和该连通块的 "所有环的边权和的 gcd" $d$，那么有解当且仅当 $d \mid w - w_0$。
加边时，如果 $u, v$ 连通，则直接更新环上 $\gcd$ (原来的 $\gcd$ 与加边前的 $\mathrm{dist}(u, v)$ 再取一遍 $\gcd$)。若不连通，则解一个方程更新 $w_i$，然后合并 $\gcd$。
总时间复杂度 $O \left( n + m \log w \right)$。
#include <bits/stdc++.h>
#define N 100005
typedef long long ll;
const int mask = 0x3fffffff;
int n, q, ans;
int p[N], st[N];
ll w[N], g[N];
inline ll gcd(ll x, ll y) {return llabs(std::__gcd(x, y));}
int ancestor(int x) {
int i = 0;
for (; x != p[x]; st[++i] = x, x = p[x]);
for (st[i + 1] = x; i; p[st[i]] = x, --i) w[st[i]] += w[st[i + 1]];
return x;
}
int main() {
int i, op, u, v, _x, _y, success; ll wt, diff;
scanf("%d%d%*d%*d", &n, &q);
for (i = 1; i <= n; ++i) p[i] = i;
for (; q; --q) {
scanf("%d%d%d%lld%d%d", &op, &u, &v, &wt, &_x, &_y);
ancestor(u = (u + (_x & ans) - 1) % n + 1);
ancestor(v = (v + (_y & ans) - 1) % n + 1);
diff = w[u] - w[v] + wt; u = p[u]; v = p[v];
if (op) {
success = u == v && !(g[u] ? diff % g[u] : diff);
putchar(48 | success); putchar(10);
ans = (ans << 1 | success) & mask;
} else
if (u == v) g[u] = gcd(g[u], diff);
else w[v] = diff, g[u] = gcd(g[u], g[v]), p[v] = u;
}
return 0;
}
坑1：注意 abs() 函数只适用于 int 类型，如果要对 long long 使用则要用 llabs()！