Background

Define the variance of a sequence $a$ of length $n$ as:

Here, $\sum$ is the summation symbol. For example, $\sum_{i=1}^5 a_i=a_1+a_2+a_3+a_4+a_5$. $\overline{a}$ is the average of the sequence $a$.

For example, for the sequence $\{3,5,1,4,2\}$, $\overline{a}=3$. Then $s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2=\frac{1}{5}[(3-3)^2+(5-3)^2+(1-3)^2+(4-3)^2+(2-3)^2]=2$.

Problem Description

Xiao S thinks math is very easy, so Xiao R wants to test her.

Xiao R gives Xiao S a sequence $a$. This sequence consists of $m$ segments. The $i$-th segment is given as l r b, meaning $a_l,a_{l+1},\ldots,a_r$ are all equal to $b$. It is guaranteed that any two given intervals do not overlap.

Now, Xiao R has $q$ queries. Each query is of the form l r, asking you to query the variance $s^2$ of the interval $[l,r]$ (note that $l$ may equal $r$, in which case the variance of this interval is $0$).

Since the number may be a decimal, Xiao R finds it inconvenient to judge the answer directly, so he wants Xiao S to compute $(r-l+1)^2\cdot s^2\bmod 998244353$. It can be proven that $(r-l+1)^2\cdot s^2$ is always an integer.

As Xiao S’s good friend, can you help her?

Input Format

The first line contains three positive integers $n,m,q$, representing the length of the sequence, the number of segments, and the number of queries.

The next $m$ lines each contain three positive integers, representing $l_i,r_i,b_i$.

The next $q$ lines each contain two positive integers $x,y$. You need to answer the variance for $[x,y]$.

Output Format

For each query, output one integer per line, representing your answer.

5 3 15
1 1 5
2 2 7
3 5 8
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

0
4
14
24
34
0
1
2
3
0
0
0
0
0
0

Hint

Sample Explanation

The sequence $a$ is $\{ 5, 7, 8, 8, 8 \}$. For the 12th query, the average of interval $[3, 5]$ is $\overline{a} = 8$, and the variance is $s^2 = \frac{1}{3} [(8 - 8)^2 + (8 - 8)^2 + (8 - 8)^2] = 0$.

Constraints

• For $20\%$ of the testdata, $n,q\leq 100$.
• For $50\%$ of the testdata, $n\leq 10^6$ and $m\leq 10^3$.
• For another $10\%$ of the testdata, $r_i-l_i\leq 1000$ and $q \leq 10^4$.
• For another $10\%$ of the testdata, $m\leq 10^3$.

For all testdata, it is guaranteed that:

• $1\leq l_i\leq r_i\leq n\leq 10^{18}$, $1\leq m\leq \min(n,2\times 10^5)$, $1\leq q\leq 2\times 10^5$, $1\leq x\leq y\leq n$, $1\leq b_i\leq 10^{18}$.
• The testdata guarantees that for any $i<j$, $l_i<l_j$, and $[l_i,r_i]$ and $[l_j,r_j]$ do not intersect, i.e. $[l_i,r_i]\cap[l_j,r_j]=\varnothing$.
• The testdata guarantees that if we take the union of all $[l_i,r_i]$, then it covers all positive integers on $[1,n]$. That is: $\bigcup_{i=1}^n[l_i,r_i] \cap \Z=[1,n] \cap \Z$.

Translated by ChatGPT 5