Variance Query on a Segmented Sequence

Little S thinks mathematics is very simple, so Little R decides to challenge her with a problem. Little R gives Little S a sequence a that is constructed from m disjoint segments. The i-th segment is given by three integers l, r and b, meaning that for all indices i with l ≤ i ≤ r, a_i = b. It is guaranteed that any two segments do not intersect.

Now, Little R poses q queries. Each query consists of two integers l and r and asks you to compute the variance s² of the interval [l, r]. (Note: when l = r, the variance is defined to be 0.) However, as the variance may be a non-integer, Little R asks Little S to compute

\[(r-l+1)^2 \cdot s^2 \bmod 998244353\]

It can be proven that \((r-l+1)^2 \cdot s^2\) is always an integer.

Definition: For an interval \([l, r]\) with \(n = r-l+1\), let

\[\text{mean} = \frac{1}{n}\sum_{i=l}^{r} a_i, \quad \text{and} \quad s^2 = \frac{1}{n}\sum_{i=l}^{r} (a_i - \text{mean})^2 = \frac{n\cdot \sum_{i=l}^{r} a_i^2 - \left(\sum_{i=l}^{r} a_i\right)^2}{n^2}.\]

Your task is to compute the value \(n\cdot \sum_{i=l}^{r} a_i^2 - \left(\sum_{i=l}^{r} a_i\right)^2 \bmod 998244353\) for each query.

inputFormat

The first line contains two integers m and q representing the number of segments and the number of queries.

The next m lines each contain three integers l, r, and b, meaning that for every index i in \([l, r]\), a_i = b. It is guaranteed that the segments do not overlap.

The following q lines each contain two integers l and r representing a query.

outputFormat

For each query, output a single line containing the value of \((r-l+1)^2 \cdot s^2 \bmod 998244353\), which is equivalent to
\(n \cdot \sum_{i=l}^{r} a_i^2 - (\sum_{i=l}^{r} a_i)^2 \bmod 998244353\) with \(n = r-l+1\).

sample

2 2
1 3 1
4 5 3
1 3
2 5

0
16