题目背景

定义一个长度为 $n$ 的序列 $a$ 的方差为：

其中：$\sum$ 为累加求和符号，例如 $\sum_{i=1}^5 a_i=a_1+a_2+a_3+a_4+a_5$。$\overline{a}$ 为序列 $a$ 的平均数。

例如对于序列 $\{3,5,1,4,2\}$，$\overline{a}=3$，此时 $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$。

题目描述

小 S 认为数学很简单，于是小 R 想要考考她。

小 R 给了小 S 一个序列 $a$，这个序列由 $m$ 段构成，第 $i$ 段被表示为 l r b，表示 $a_l,a_{l+1},\ldots,a_r$ 为 $b$，保证给出的任意两个区间不相交。

现在，小 R 有 $q$ 个问题。形如 l r，想让你查询区间 $[l,r]$ 的方差 $s^2$（需要注意：$l$ 可能等于 $r$，此时该段方差为 $0$）。

由于这个数字可能是个小数，小 R 不方便对答案，所以他想要小 S 求出 $(r-l+1)^2\cdot s^2\bmod 998244353$。可以证明 $(r-l+1)^2\cdot s^2$ 一定是整数。

作为小 S 的好朋友，你能帮帮她吗？

输入格式

第一行三个正整数 $n,m,q$，表示序列的长度，序列的段数和问题的个数。

接下来 $m$ 行，每行三个正整数，分别表示 $l_i,r_i,b_i$。

接下来 $q$ 行，每行两个正整数 $x,y$。你需要回答 $[x,y]$ 的方差。

输出格式

对于每个询问，输出一行一个整数，表示你的答案。

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

提示

【样例解释】

序列 $a$ 为 $\{ 5, 7, 8, 8, 8 \}$。对于第 $12$ 组询问，区间 $[3, 5]$ 的平均数 $\overline{a} = 8$，方差 $s^2 = \frac{1}{3} [(8 - 8)^2 + (8 - 8)^2 + (8 - 8)^2] = 0$。

【数据范围】

• 对于 $20\%$ 的数据，保证 $n,q\leq 100$。
• 对于 $50\%$ 的数据，保证 $n\leq 10^6$，$m\leq 10^3$。
• 对于另外 $10\%$ 的数据，保证 $r_i-l_i\leq 1000$，$q \leq 10^4$。
• 对于另外 $10\%$ 的数据，保证 $m\leq 10^3$。

对于所有数据，保证：

• $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}$。
• 数据保证对于任意 $i<j$，$l_i<l_j$，且 $[l_i,r_i]$ 与 $[l_j,r_j]$ 不存在交集，即 $[l_i,r_i]\cap[l_j,r_j]=\varnothing$。
• 数据保证，若将所有的 $[l_i,r_i]$ 取并集，则其覆盖了 $[1,n]$ 上所有的正整数。即：$\bigcup_{i=1}^n[l_i,r_i] \cap \Z=[1,n] \cap \Z$。