TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

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$.

Input Format

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

Output Format

Sample Input 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

Sample Output 1

1
-1
1
1
0
1
998244254
99
999
0

Hints

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

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152