Problem Description

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<r_i\leq n$. Then $x_i=\max\limits_{j=1}^m\{l_j \mid l_j+1\leq i\leq r_j\}$. In particular, if for all $1\leq j\leq m$, it is not true that $l_j+1\leq i\leq r_j$, then $x_i=0$.

Now ZHY has fully understood his learning ability, but the previous attempts made him exhausted, so he decided to rest for $1$ second, and hopes you can help him compute the expected number of minutes he needs to finish learning. However, he realized that learning each work for a fixed $1$ minute is not comprehensive enough, so he decided to change the one minute he spends on some works, which will change the success probability of learning that work. Specifically, ZHY now提出 (pinyin: tichu) $k$ requests, and each request is one of the following two types:

1. Modify the success probability $P_i$ of some work $i$.
2. Query the expected number of minutes needed to finish learning all $n$ works under the current probabilities.

Since ZHY needs to rest, he turned to you and hopes you can handle his requests. For each request of the second type, you should output the expected time modulo $10^9+7$. ZHY gave you $1$ second, because he can only rest for that long.

Input Format

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$.

Output Format

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

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

10
9

2 1 1
1 1
1 2
0 2
2

4

2 1 1
1 1
1 2
1 2
2

3

Hint

This problem uses bundled testdata.

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<r_j$.

For $100\%$ of the data, $1 \le n,k \le 10^5$, $0 \le m \le 10^5$, $1 \le p_{i} \le q_{i} \lt 10^{9}+7$, $0 \le l_{i} \lt r_{i} \le n$.

Translated by ChatGPT 5