带权并查集

【题目描述】

有一个未知的整数序列 $(a_0, \ldots, a_{N - 1})$，请处理 $Q$ 次查询。

• $t_i$ = 0 $u_i$ $v_i$ $x_i$：给出信息 $a_u \equiv a_v + x \pmod{998244353}$。当该信息不与此前给出的任何有效信息矛盾时，该信息有效。若该信息有效，输出 $1$；否则输出 $0$。

• $t_i$ = 1 $u_i$ $v_i$：根据目前给出的有效信息，如果可以确定 $a_u - a_v \bmod 998244353$ 的值，则输出该值；否则输出 $-1$。

【输入】

$N$ $Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对于每个查询，按照题意输出一行。

【输入样例】

4 10
0 1 0 9
1 0 2
0 2 1 90
0 2 0 99
0 0 2 123
0 3 1 990
1 0 2
1 2 0
1 3 0
1 1 1

【输出样例】

1
-1
1
1
0
1
998244254
99
999
0

【数据范围】

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq u_i, v_i \lt N$
• $0 \leq x_i \lt 998244353$

【来源】

Library Checker（yosupo06） unionfind_with_potential