7834: [yosupo] Data Structure - Unionfind with Potential
[Creator : ]
Description
There is an unknown sequence of integers $(a_0, \ldots, a_{N - 1})$, process $Q$ queries.
- `$t_i$ = 0 $u_i$ $v_i$ $x_i$`: You are provided with information that $a_u \equiv a_v + x \pmod{998244353}$. This information is valid if it does not contradict any previously given valid information. If this information is valid, output $1$; otherwise, output $0$.
- `$t_i$ = 1 $u_i$ $v_i$`: Based on the valid information provided so far, output the value of $a_u - a_v \bmod 998244353$ if it can be determined; otherwise, output $-1$.
- `$t_i$ = 0 $u_i$ $v_i$ $x_i$`: You are provided with information that $a_u \equiv a_v + x \pmod{998244353}$. This information is valid if it does not contradict any previously given valid information. If this information is valid, output $1$; otherwise, output $0$.
- `$t_i$ = 1 $u_i$ $v_i$`: Based on the valid information provided so far, output the value of $a_u - a_v \bmod 998244353$ if it can be determined; otherwise, output $-1$.
Input
$N$ $Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$
Output
Q line, print the answer.
Constraints
- $1 \leq N \leq 2\times 10^5$
- $1 \leq Q \leq 2\times 10 ^5$
- $0 \leq u_i, v_i \lt N$
- $0 \leq x_i \lt 998244353$
- $1 \leq Q \leq 2\times 10 ^5$
- $0 \leq u_i, v_i \lt N$
- $0 \leq x_i \lt 998244353$
Sample 1 Input
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
Sample 1 Output
1
-1
1
1
0
1
998244254
99
999
0