P10256 Highly Imitated Migos

After hard training, ZHY finally became a rapper. But one day, rapper ZHY saw works by the peer rap group Migos, and immediately realized the gap between them. So he wants to learn Migos' rap skills and reproduce Migos' success. After researching for several days and nights, ZHY finally selected $n$ rap works of Migos, numbered $1,2,\dots,n$ in order. He believes that as long as he finishes learning these $n$ works, he can become a better rapper. Therefore, he will start from work $1$, and learn them one by one in increasing order. After finishing work $n$, he ends his learning. However, rapper ZHY has a very special way of learning. For each work, he only listens for $1$ minute. The problem with this learning method is that for work $i$, after spending $1$ minute, he may succeed or fail. Specifically, if ZHY is learning work $i$, then after he spends one minute learning: - With probability $P_i$, ZHY succeeds, and then he will continue to learn work $i+1$ (of course, if $i=n$, he ends the learning directly). - With probability $1-P_i$, ZHY fails. Unfortunately, the memory in his brain will become confused, causing him to remember only the first $x_i$ works, i.e. he must restart learning from work $x_i+1$. After trying to learn several times, ZHY was deeply troubled by the memory confusion, so he asked brain science expert YHZ for help. After YHZ's research, he found that all $x_i$ follow a certain pattern. Specifically, he found $m$ pairs of natural numbers $(l_i,r_i)$, where $i=1,2\dots,m$, satisfying $0\leq l_i

The first line contains three integers $n,m,k$, with the meaning as described above. In the next $n$ lines, each line contains two positive integers $p_i,q_i$, meaning $P_i=\frac{p_i}{q_i}$. In the next $m$ lines, each line contains two integers $l_{i},r_{i}$. In the next $k$ lines, each line is in one of the following two formats: - `1 x a b` is a modification operation, meaning $P_x$ becomes $\frac a b$. It is guaranteed that $1\le x \le n$, $1 \le a \le b < 10^9+7$, and $x,a,b$ are all positive integers. - `2` is a query operation, meaning to ask what the expected time to finish learning is at this moment, modulo $10^9+7$.

For each query, output one integer per line representing the answer.

**This problem uses bundled testdata.** | Subtask ID | $n$ | $m$ | $k$ | Special Property | Score | | :-----: | :-----: | :-----: | :-----: | :-----: | :-----: | | $0$ | $\le 300$ | $\le 300$ | $\le 300$ | None | $11$ | | $1$ | $\le 3000$ | $\le 3000$ | $\le 3000$ | None | $4$ | | $2$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | B | $5$ | | $3$ | $\le 10^5$ | $\le 10^5$ | $\le 1$ | None | $14$ | | $4$ | $\le 10^5$ | $=0$ | $\le 10^5$ | None | $19$ | | $5$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | A | $19$ | | $6$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | B | $8$ | | $7$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | C | $10$ | | $8$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | None | $10$ | All “intervals” below refer to $[l_i,r_i]$. Special Property A: It is guaranteed that for all $i \in [1,m]$, $r_i-l_i+1\le 5$. Special Property B: It is guaranteed that the intersections of these intervals are all $\le 1$. That is, for all $i,j \in [1,m]$ with $i\ne j$, we have $r_i\le l_j$ or $r_j\le l_i$. Special Property C: It is guaranteed that these intervals have no containment relationship. That is, for all $i,j \in [1,m]$ with $i\ne j$, we have $l_i>l_j$ or $r_i