포텐셜이 있는 유니온 파인드 (비가환군)

정수 성분을 갖는 $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$을 출력한다.

제약 조건

• $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}$

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

$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$을 출력한다.