Segment Tree Tutorial
Description
You are given an $n$-dimensional hypercube with side length $10^5$. The hypercube contains $(10^5)^n$ cells, each of which is labeled with a unique $n$-integer tuple $(p_1, p_2, ..., p_n)$ such that for all $i$, $1 \leq p_i \leq 10^5$. Additionally, each cell contains a single integer, which is initially set to $0$.
Your task is to process $q$ of the following two types of queries:
- ADD $(l_1, r_1), (l_2, r_2), ..., (l_n, r_n), x$: For all cells labelled $(p_1, p_2, ..., p_n)$ such that for all $i$, $l_i \leq p_i \leq r_i$, increment the value they each contain by $x$.
- SUM $(l_1, r_1), (l_2, r_2), ..., (l_n, r_n)$: Compute the sum of all integers held by cells labelled $(p_1, p_2, ..., p_n)$ such that for all $i$, $l_i \leq p_i \leq r_i$. Since the sum can be large, please output it modulo $998244353$.
It is guaranteed that for all queries, for all $i$, $l_i$ and $r_i$ have been picked uniformly at random from all $\binom{10^5 + 1}{2}$ possible choices.
The first line of input consists of two space-separated integers $n$ and $q$ $(1 \leq n \leq 500, 1 \leq q \leq 3000)$.
The next $q$ lines each consist of a query, which is described by one of the following:
- The string ADD followed by a space, followed by $2n + 1$ space-separated integers $l_1, r_1, l_2, r_2, ..., l_n, r_n, x$ $(1 \leq l_i \leq r_i \leq 10^5, 0 \leq x < 998244353)$.
- The string SUM followed by a space, followed by $2n$ space-separated integers $l_1, r_1, l_2, r_2, ..., l_n, r_n$ $(1 \leq l_i \leq r_i \leq 10^5)$.
It is guaranteed that for all queries, for all $i$, $l_i$ and $r_i$ have been picked uniformly at random from all $\binom{10^5 + 1}{2}$ possible choices.
If there are $k$ SUM queries, output $k$ lines. The $i$th line should contain the answer to the $i$th SUM query, modulo $998244353$.
Input
The first line of input consists of two space-separated integers $n$ and $q$ $(1 \leq n \leq 500, 1 \leq q \leq 3000)$.
The next $q$ lines each consist of a query, which is described by one of the following:
- The string ADD followed by a space, followed by $2n + 1$ space-separated integers $l_1, r_1, l_2, r_2, ..., l_n, r_n, x$ $(1 \leq l_i \leq r_i \leq 10^5, 0 \leq x < 998244353)$.
- The string SUM followed by a space, followed by $2n$ space-separated integers $l_1, r_1, l_2, r_2, ..., l_n, r_n$ $(1 \leq l_i \leq r_i \leq 10^5)$.
It is guaranteed that for all queries, for all $i$, $l_i$ and $r_i$ have been picked uniformly at random from all $\binom{10^5 + 1}{2}$ possible choices.
Output
If there are $k$ SUM queries, output $k$ lines. The $i$th line should contain the answer to the $i$th SUM query, modulo $998244353$.
1 5
SUM 80990 92828
ADD 73356 82192 15
SUM 4355 39641
ADD 10847 85692 67
SUM 10750 13698
2 6
ADD 59731 94993 24909 93877 2273
SUM 26347 68751 34850 79984
ADD 7811 91704 14253 48118 12634
SUM 57180 64491 33935 67473
ADD 18494 42024 70782 71906 13972
ADD 65552 83196 57079 87722 7732
0
0
191084
108608724
208434911
Note
In the first sample test case, the answer to the first SUM query is $0$ since no ADD queries have occurred yet.
The answer to the second SUM query is also $0$, since no ADD queries have modified the values of the cells in that region.
The answer to the third SUM query is $(13698 - 10847 + 1) \cdot 67 = 191084$.