9080: Random Addition

链接：https://ac.nowcoder.com/acm/contest/57361/A
来源：牛客网
Daniel and sszcdjr are playing a game. The game is played on a sequence $a$ of length $n$. Initially, all elements in $a$ are equal to $0$. They will do the following operations $m$ times on it:

* Daniel selects one segment [li,ri][l_i,r_i][li,ri] (1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n);
* Then, sszcdjr chooses a real number $x$ such that $0\le x\le 1$ \bf{uniformly at random};
* For all li≤j≤ril_i\le j\le r_ili≤j≤ri, set aj:=aj+xa_j:=a_j+xaj:=aj+x.

However, sszcdjr thinks it is unfair for him. So he adds a rule: for any two segments [li,ri][l_i,r_i][li,ri] and [lj,rj][l_j,r_j][lj,rj] ($i\ne j$), one of the following condition must holds:

* The two segments are completely disjoint. More formally, either li≤ri<lj≤rjl_i\le r_i<l_j\le r_jli≤ri<lj≤rj or lj≤rj<li≤ril_j\le r_j<l_i\le r_ilj≤rj<li≤ri;
* One of the two segments are inside another. More formally, either li≤lj≤rj≤ril_i\le l_j\le r_j\le r_ili≤lj≤rj≤ri or lj≤li≤ri≤rjl_j\le l_i\le r_i\le r_jlj≤li≤ri≤rj.

Note that two segments can be exactly the same.

Let $s$ be the maximum number in $a$ after the operations. zxx is crazy about probabilities, so he gives you $t$ queries. In each query, he gives you two numbers $P$, $Q$, and asks you the probability that P≤s≤QP\le s\le QP≤s≤Q. You just need to tell him the answer modulo $998244353$.

The first line of input contains three integers $n$, $m$, $t$ (1≤n≤1061\leq n\leq 10^61≤n≤106, $1\le m\le 200$ 1≤t≤5×1051\leq t\leq 5\times 10^51≤t≤5×105) --- the length of the sequence, the number of operations and the number of queries.
Then $m$ lines follow, the $i$-th line contains two integers lil_ili, rir_iri (1≤li≤ri≤n1\le l_i\le r_i\le n1≤li≤ri≤n) --- the segment in the $i$-th operation.
In the following $t$ lines, each line contains two integers $p$, $q$ (0≤p<q≤1070\le p<q\le 10^70≤p<q≤107) --- the two numbers piggy give you in the query are equal to P=p⋅10−6P=p\cdot 10^{-6}P=p⋅10−6 and Q=q⋅10−6Q=q\cdot 10^{-6}Q=q⋅10−6 .

For each query print an integer --- the probability that P≤s≤QP\le s\le QP≤s≤Q, modulo $998244353$.
Formally, let M=998244353M = 998\,244\,353M=998244353. It can be shown that the answer can be expressed as an irreducible fraction pq\frac{p}{q}qp, where $p$ and $q$ are integers and q≢0(modM)q \not \equiv 0 \pmod{M}q≡0(modM). Output the integer equal to p⋅q−1modMp \cdot q^{-1} \bmod Mp⋅q−1modM. In other words, output such an integer $x$ that $0\le x<M$ and x⋅q≡p(modM)x \cdot q \equiv p \pmod{M}x⋅q≡p(modM).