带权并查集（非交换群）

【题目描述】

存在一个未知的、元素均为整数的 $2 \times 2$ 可逆矩阵序列 $(a_0, \ldots, a_{N - 1})$，请处理 $Q$ 个查询。

• $t_i$ = 0 $u_i$ $v_i$ $x_{0, 0}$ $x_{0, 1}$ $x_{1, 0}$ $x_{1, 1}$：给出信息 $a_u \equiv a_v x \pmod{998244353}$，其中 $x$ 是元素为 $x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1}$ 的 $2 \times 2$ 矩阵。若这条信息与之前给出的任何有效信息都不矛盾，则它是有效的。若该信息有效，输出 $1$；否则输出 $0$。
• $t_i$ = 1 $u_i$ $v_i$：根据目前给出的有效信息，若 $a_v^{-1}a_u \bmod 998244353$ 的值可以被确定，则输出该值；否则输出 $-1$。

【输入】

输入按以下格式给出：

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

【输出】

按读入顺序输出每个查询的结果。

• 对 $t_i$ = 0 的查询：若给出的信息有效，输出 $1$；否则输出 $0$。
• 对 $t_i$ = 1 的查询：若 $a_v^{-1}a_u \bmod 998244353$ 的值可以被确定，则输出该值；否则输出 $-1$。

【输入样例】

4 10
0 1 0 2 998244350 998244350 5
1 0 2
0 2 1 1 2 3 7
0 2 0 998244346 998244336 12 29
0 0 2 1 2 1 3
0 3 1 2 0 0 499122177
1 0 2
1 2 0
1 3 0
1 1 1

【输出样例】

1
-1
1
1
0
1
29 17 998244341 998244346
998244346 998244336 12 29
4 499122175 998244347 499122179
1 0 0 1

【数据范围】

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq u_i, v_i \lt N$
• $0 \leq x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1} < 998244353$
• $x_{0, 0}x_{1, 1} - x_{0, 1}x_{1, 0} \equiv 1 \pmod {998244353}$

【来源】

Library Checker（yosupo06） unionfind_with_potential_non_commutative_group