Background

YSGHYYDS.

Problem Description

YSGH prepared $n$ problems for a contest. The difficulty of problem $i$ is $d_i$, and its value is $c_i$.

There are $m$ potential contestants. Contestant $i$ participates in the contest with probability $p_i$. If contestant $i$ participates, then they will solve exactly all problems whose difficulties are between $l_i$ and $r_i$ (including $l_i$ and $r_i$).

The contest committee will finally award YSGH a bonus equal to the $k$-th power of the sum of values of all problems that are solved by at least one contestant. In particular, we define $0^0 = 1$.

You need to help YSGH compute the expected value of the bonus.

Let $P=998244353$. Suppose a rational number $x$ is written in lowest terms as $\frac{a}{b}$. If $\gcd(b,P)=1$, then there exists a unique integer $c$ ($0 \le c < P$) such that $b c \equiv a \pmod{P}$. We call this $c$ the value of $x$ modulo $P$.

It can be proven that even if only the value of $p_i$ modulo $P$ is given, the answer still exists uniquely modulo $P$.

Input Format

The first line contains three integers $n, m, k$, representing the number of problems, the number of potential contestants, and the parameter used to compute the bonus.

The next $n$ lines each contain two integers $d_i, c_i$, representing the difficulty and value of problem $i$.

The next $m$ lines each contain three integers $l_i, r_i, p_i$, representing the difficulty interval of problems that contestant $i$ can solve, and the probability (given modulo $P$) that they participate in the contest.

Output Format

Output one line with one integer, representing the expected value of the bonus modulo $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

Hint

Sample Explanation #1

This sample satisfies Special Property A.

If the first person participates, they can solve problems $1, 2, 5$.

If the second person participates, they can solve problem $3$.

So the expected bonus of YSGH is $(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}$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $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$.

The special constraints and scores of each Subtask are as follows:

Special Property A: For any $1\le i < j\le M$, we have $[l_i,r_i]\cap [l_j,r_j]=\varnothing$.

Translated by ChatGPT 5