带权并查集（非交换群）（Unionfind with Potential (Non-Commutative Group)）

问题描述

给定一个未知的 $2 \times 2$ 可逆整数矩阵序列 $(a_0, \dots, a_{N-1})$，请处理以下 $Q$ 个查询：

• 0 u v x₀₀ x₀₁ x₁₀ x₁₁：你被告知 $a_u \equiv a_v \cdot x \pmod{998244353}$，其中 $x = \begin{bmatrix} x_{0,0} & x_{0,1} \\ x_{1,0} & x_{1,1} \end{bmatrix}$ 是一个 $2 \times 2$ 矩阵。若该信息与此前所有有效信息不矛盾，则输出 1；否则输出 0。
• 1 u v：基于迄今所有有效信息，若 $a_v^{-1} a_u \bmod 998244353$ 可被唯一确定，则输出其值；否则输出 -1。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq u_i, v_i < N$
• $0 \leq x_{i,0}, x_{i,1}, x_{i,0}, x_{i,1} < 998244353$
• $x_{0,0} x_{1,1} - x_{0,1} x_{1,0} \equiv 1 \pmod{998244353}$

输入格式

$N\ Q$
$Query_0$
$Query_1$
:
$Query_{Q-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