P10511 Variance

Define the variance of a sequence $a$ of length $n$ as: $$s^2=\frac{1}{n} \sum_{i=1}^n (a_i-\overline{a})^2$$ 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$.

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?

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

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

**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