P7483 50 年后的我们

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$ 意义下的值。

**【样例解释 \#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$ | $400$ | $1$ | 无 | $6$ | | $3$ | $400$ | $2$ | 特殊性质 A | $7$ | | $4$ | $400$ | $2$ | 无 | $8$ | | $6$ | $18$ | $100$ | 特殊性质 A | $3$ | | $5$ | $18$ | $100$ | 无 | $15$ | | $7$ | $100$ | $100$ | 特殊性质 A | $9$ | | $8$ | $100$ | $100$ | 无 | $16$ | | $9$ | $400$ | $400$ | 特殊性质 A | $10$ | | $10$ | $400$ | $400$ | 无 | $21$ | 特殊性质 A：对于任意 $1\le i < j\le M$，都有 $[l_i,r_i]\cap [l_j,r_j]=\varnothing$。