Expected Competition Bonus

You are given a competition with \(n\) problems. The \(i\)-th problem has difficulty \(d_i\) and value \(c_i\). There are \(m\) potential contestants. The \(i\)-th contestant participates in the contest with probability \(p_i\) (the value of \(p_i\) is given in modulo \(P=998244353\) arithmetic). If a contestant participates, they will correctly solve every problem with difficulty in the range \([l_i, r_i]\) (inclusive).

Let \(S\) be the sum of the values \(c_i\) of all problems that are solved by at least one contestant. The bonus is defined as \(S^k\), where \(k\) is a nonnegative integer. In particular, we define \(0^0=1\). You are to compute the expected bonus.

More formally, the bonus is computed as \(\Bigl( \sum_{i=1}^{n} c_i \cdot I_i \Bigr)^k\), where \(I_i=1\) if problem \(i\) is solved (i.e. there exists at least one contestant who participates and whose range covers \(d_i\)), and \(I_i=0\) otherwise.

All calculations are performed under modulo \(P=998244353\). More specifically, for a rational number \(x=\frac{a}{b}\) in simplest form, if \(\gcd(b, P)=1\), there exists a unique integer \(c\) (\(0 \le c < P\)) such that \(b \cdot c \equiv a \pmod{P}\); we say that \(x\) equals \(c\) modulo \(P\). It can be shown that the answer is unique modulo \(P\) even if only the values of \(p_i\) modulo \(P\) are provided.

inputFormat

The input begins with a single line containing three integers \(n\), \(m\), and \(k\) \( (1\le n, m \le 20) \) representing the number of problems, the number of potential contestants, and the exponent respectively.

Then follow \(n\) lines, each containing two integers \(d_i\) and \(c_i\) \( (1 \le d_i, c_i \le 10^9) \), representing the difficulty and value of the \(i\)-th problem.

After that, there are \(m\) lines. The \(i\)-th of these lines contains three integers: \(p_i\) \( (0\le p_i < 998244353) \), \(l_i\), and \(r_i\) \( (1\le l_i\le r_i\le 10^9) \). Here, \(p_i\) represents the probability (in modulo \(998244353\)) that the \(i\)-th contestant participates; if the contestant participates, they solve every problem with difficulty between \(l_i\) and \(r_i\) (inclusive).

outputFormat

Output a single integer denoting the expected bonus modulo \(998244353\).

sample

2 2 1
1 5
3 10
1 1 2
0 3 3

5