TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

You are given a $10^ {9} \times 10^ {9}$ matrix $A = (A_ {xy})$ ($0\leq x < 10^ {9}$, $0\leq y < 10^ {9}$).
Initially, all entries $A_ {xy}$ equal $0$.

First, process following $N$ queries.

  • l d r u w: Add $w$ to all entries $A_ {xy}$ satisfying $l\leq x < r$ and $d\leq y < u$.

Then, process following $Q$ queries.

  • l d r u: Calculate sum of entries $A_ {xy}$ satisfying $l\leq x < r$ and $d\leq y < u$, and print it modulo $998244353$.

Input Format

$N$ $Q$
$l_ 0$ $d_ 0$ $r_ 0$ $u_ 0$ $w_ 0$
$\vdots$
$l_ {N-1}$ $d_ {N-1}$ $r_ {N-1}$ $u_ {N-1}$ $w_ {N-1}$
$l_ 0$ $d_ 0$ $r_ 0$ $u_ 0$
$\vdots$
$l_ {Q-1}$ $d_ {Q-1}$ $r_ {Q-1}$ $u_ {Q-1}$

Output Format

Sample Input 1

2 7
0 0 2 4 1
1 1 3 5 2
0 0 1 1
1 1 2 2
2 2 3 3
0 0 3 5
0 0 3 2
0 1 3 3
3 0 4 4

Sample Output 1

1
3
2
24
8
12
0

Hints

  • $1 \leq N \leq 2 \times 10^ {5}$
  • $1 \leq Q \leq 2 \times 10^ {5}$
  • $0 \leq l_ i < r_ i \leq 10^ {9}$
  • $0 \leq d_ i < u_ i \leq 10^ {9}$
  • $0 \leq w_ i < 998244353$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 2097152 2097152
1 10000 2097152 2097152
2 10000 2097152 2097152
3 10000 2097152 2097152
4 10000 2097152 2097152
5 10000 2097152 2097152
6 10000 2097152 2097152
7 10000 2097152 2097152
8 10000 2097152 2097152
9 10000 2097152 2097152
10 10000 2097152 2097152
11 10000 2097152 2097152
12 10000 2097152 2097152