Problem Description

After rigorous training, ZHY has finally become a rapper. However, upon seeing the works of the fellow rap group Migos, ZHY immediately realized the gap between them and decided to learn Migos' rap techniques to replicate their success.

After days of research, ZHY selected $n$ rap works by Migos, numbered sequentially from $1$ to $n$. He believes that by studying these $n$ works, he can become a more outstanding rapper. Therefore, he will start from the first work and study them in ascending order of their numbers, ending with the $n$-th work.

However, ZHY's learning method is peculiar. For each work, he only listens for 1 minute. The issue with this method is that for the $i$-th work, after investing 1 minute, he might succeed or fail. Specifically, if ZHY is studying work $i$, then after spending one minute on it:

• There is a probability of $P_i$ that ZHY succeeds in learning, and he will then move on to study work $i+1$ (or end if $i=n$).
• There is a probability of $1-P_i$ that ZHY fails. Unfortunately, this failure causes confusion in his memory, making him remember only the first $x_i$ works, meaning he must restart from work $x_i+1$.

ZHY, troubled by the memory confusion after several attempts, sought help from neuroscientist YHZ. After research, YHZ 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$, such that $x_i = \max\limits_{j=1}^m \{l_j \mid l_j+1 \leq i \leq r_j\}$. Notably, if for all $1 \leq j \leq m$, none satisfy $l_j+1 \leq i \leq r_j$, then $x_i = 0$.

Now, ZHY has a good understanding of his learning ability but is exhausted from the previous attempts. He decides to rest for 1 second and hopes you can calculate the expected number of minutes he needs to finish learning. However, he realizes that learning each work for a fixed 1 minute is not comprehensive enough, so he decides to change the probability of success for some works. Specifically, ZHY has $k$ requests, each being either:

1. Modify the success probability $P_i$ for a work $i$.
2. Query the expected time to finish learning with the current probabilities, modulo $10^9+7$.

Since ZHY needs to rest, he asks you to handle his requests. For each second type of request, you need to output the expected time modulo $10^9+7$. ZHY gives you 1 second, as that's how long he can rest.

Input Format

The first line contains three integers $n, m, k$. These represent the number of works, the number of pairs, and the number of requests, respectively.

The next $n$ lines each contain two positive integers $p_i, q_i$, indicating $P_i = \frac{p_i}{q_i}$.

The next $m$ lines each contain two integers $l_i, r_i$.

The next $k$ lines each contain one of the following formats:

• 1 x a b for a modification operation, indicating $P_x$ is changed to $\frac{a}{b}$. It is guaranteed that $1 \leq x \leq n$, $1 \leq a \leq b < 10^9+7$, and $x, a, b$ are positive integers.
• 2 for a query operation, asking for the expected time to finish learning, modulo $10^9+7$.

Output Format

For each query, output one line containing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

10
9

Input Sample #2

2 1 1
1 1
1 2
0 2
2

Output Sample #2

4

Input Sample #3

2 1 1
1 1
1 2
1 2
2

Output Sample #3

3

Notes/Hints

This problem uses batched testing.

The term "interval" refers to $[l_i, r_i]$.

Special Condition A: For all $i \in [1, m]$, $r_i - l_i + 1 \leq 5$.

Special Condition B: The intersections of these intervals are at most 1. That is, for all $i, j \in [1, m]$ and $i \neq j$, either $r_i \leq l_j$ or $r_j \leq l_i$.

Special Condition C: These intervals do not contain each other. That is, for all $i, j \in [1, m]$ and $i \neq j$, either $l_i > l_j$ or $r_i < r_j$.

For 100% of the data, $1 \leq n, k \leq 10^5$, $0 \leq m \leq 10^5$, $1 \leq p_i \leq q_i < 10^9+7$, and $0 \leq l_i < r_i \leq n$.

见题面 Input 部分

见题面 Output 部分