#1874. 方差

方差

题目描述

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

小 R 给了小 S 一个序列 aa,这个序列由 mm 段构成,第 ii 段被表示为 l r b,表示 al,al+1,…,ara_l,a_{l+1},\ldots,a_r 为 bb,保证给出的任意两个区间不相交。

现在,小 R 有 qq 个问题。形如 l r,想让你查询区间 [l,r][l,r] 的方差 s2s^2(需要注意:ll 可能等于 rr,此时该段方差为 00)。

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

作为小 S 的好朋友,你能帮帮她吗?

输入格式

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

接下来 mm 行,每行三个正整数,分别表示 li,ri,bil_i,r_i,b_i。

接下来 qq 行,每行两个正整数 x,yx,y。你需要回答 [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

题目来源:洛谷 P10511