题目背景

YSGHYYDS

题目描述

YSGH 给一场比赛出了 $n$ 道题，第 $i$ 道题的难度为 $d_i$，价值为 $c_i$。

有 $m$ 个可能参赛的选手。第 $i$ 个选手有 $p_i$ 的概率会参加比赛。若第 $i$ 个选手参加比赛，则该选手会恰好通过难度在 $l_i$ 到 $r_i$ 之间（包括 $l_i$ 和 $r_i$）的所有题目。

比赛组委会最终给 YSGH 的奖金为所有题中，有选手通过的题的价值之和的 $k$ 次幂。特别地，我们定义 $0$ 的 $0$ 次幂等于 $1$。

YSGH 想让你帮他求出奖金的期望。

令 $P=998244353$，设一个有理数 $x$ 表示成最简分数的形式为 $\frac{a}{b}$，若 $\gcd(b,P)=1$，则存在唯一的整数 $c$（$0 \le c < P$）满足 $b c \equiv a \pmod{P}$，我们称 $x$ 在模 $P$ 意义下的值为 $c$。

可以证明，在仅给出 $p_i$ 模 $P$ 意义下的值时，答案仍然在模 $P$ 意义下唯一存在。

输入格式

第一行，三个整数 $n,m,k$，表示题目数量，可能参赛的人数，以及计算奖金需要的参数。

接下来 $n$ 行，第 $i$ 行两个整数 $d_i, c_i$，分别表示第 $i$ 道题的难度和价值。

接下来 $m$ 行，第 $i$ 行三个整数 $l_i, r_i, p_i$，分别表示第 $i$ 个选手通过的题的难度区间，以及来参加比赛的概率在模 $P$ 意义下的值。

输出格式

一行，一个整数，表示奖金的期望在模 $P$ 意义下的值。

5 2 1
346 412
464 685
895 544
976 322
612 121
346 712 2
850 932 3

4068

5 2 2
346 412
464 685
895 544
976 322
612 121
233 749 798465123
698 985 151455772

105133973

提示

【样例解释 #1】

该样例满足特殊性质 A。

第一个人若参赛，可以通过第 $1,2,5$ 题。

第二个人若参赛，可以通过第 $3$ 题。

所以 YSGH 的奖金期望为 $(412+685+121)\times 2\times (1-3)+544\times (1-2)\times 3+(412+685+121+544)\times 2\times 3\equiv 4068\pmod{P}$。

---

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le 400$，$0\le k\le 400$，$1\le m\le 10^5$，$1\le d_i\le 10^9$，$1\le l_i\le r_i\le 10^9$，$0\le c_i,p_i < 998244353$。

各 Subtask 的特殊限制与分值如下：

测试包编号	$n\le$	$k\le$	其他限制	分值
$1$	$400$	$1$	特殊性质 A	$5$
$2$			无	$6$
$3$		$2$	特殊性质 A	$7$
$4$			无	$8$
$6$	$18$	$100$	特殊性质 A	$3$
$5$			无	$15$
$7$	$100$		特殊性质 A	$9$
$8$			无	$16$
$9$	$400$		特殊性质 A	$10$
$10$			无	$21$

特殊性质 A：对于任意 $1\le i < j\le M$，都有 $[l_i,r_i]\cap [l_j,r_j]=\varnothing$。