题目描述

经过刻苦的训练，ZHY 终于成为了一名说唱歌手。但这天，说唱歌手 ZHY 看到了同行说唱组合 Migos 的作品，立刻意识到了自己的差距，于是他要学习 Migos 的说唱技巧，复刻 Migos 的成功。

经过数个日夜的研究，ZHY 最终挑选出了 $n$ 部 Migos 的说唱作品，依次编号为 $1,2,\dots,n$。他认为只要学习完这 $n$ 部作品，就可以成为更加优秀的说唱歌手。于是，他会从第 $1$ 部作品，按编号从小到大的顺序依次进行学习，学习完第 $n$ 部作品就结束学习。

不过，说唱歌手 ZHY 的学习方式很特殊。对于每部作品，他只会听 $1$ 分钟。这种学习方式的问题是，对于第 $i$ 部作品，他在投入 $1$ 分钟后，有可能学习成功，也有可能会失败，具体地，如果 ZHY 学习的是作品 $i$，那么在他花一分钟的时间进行学习后：

• 有 $P_i$ 的概率，ZHY 学习成功了，那么他会接着去学习作品 $i+1$（当然如果 $i=n$ 就直接结束学习）。
• 有 $1-P_i$ 的概率，ZHY 学习失败了。不幸的是，ZHY 脑内的记忆还会因此产生混乱，导致他只会记住前 $x_i$ 部作品，即他必须从第 $x_i+1$ 部作品开始重新学习。

ZHY 在尝试了几次学习后，深受记忆混乱的困扰，于是向脑科学专家 YHZ 求助。经过脑科学专家 YHZ 的研究，他发现所有的 $x_i$ 有一定的规律。具体地，他发现有 $m$ 对自然数 $(l_i,r_i)$, 其中 $i=1,2\dots,m$，满足 $0\leq l_i<r_i\leq n$，那么 $x_i=\max\limits_{j=1}^m\{l_j \mid l_j+1\leq i\leq r_j\}$，特别地，如果对于所有 $1\leq j\leq m$，都不满足 $l_j+1\leq i\leq r_j$，那么 $x_i=0$。

现在，ZHY 对自己的学习能力有了充分了解，但刚才的尝试让他疲惫不堪，所以他决定休息 $1$ 秒，并希望你帮他计算一下他期望多少分钟可以结束学习。不过他意识到，自己如果每部作品只学固定的 $1$ 分钟是不够全面的，所以他决定更改一些作品他所会学习的那一分钟，这会导致他学习这一部作品的成功概率发生改变。具体地，现在 ZHY 提出了 $k$ 个要求，每个要求有两种可能：

1. 修改某个作品 $i$ 学习成功的概率 $P_i$。
2. 询问以当前的概率他学习完 $n$ 部作品期望要多少分钟。

由于 ZHY 要休息，所以他找上了你，希望你来解决他的要求。对于他的每个第二种要求，你要告诉他期望时间对 $10^9+7$ 取模的结果。ZHY 给了你 $1$ 秒的时间，因为他只能休息这么久。

输入格式

第一行三个整数 $n,m,k$。意思如题面所述。

接下来 $n$ 行，每行两个正整数 $p_i,q_i$，表示 $P_i=\frac{p_i}{q_i}$。

接下来 $m$ 行，每行两个整数 $l_{i},r_{i}$。

接下来 $k$ 行，每行都是以下两种格式的其中一种：

• 1 x a b 为修改操作。表示 $P_x$ 变成了 $\frac a b$。保证 $1\le x \le n$，$1 \le a \le b < 10^9+7$ 且 $x,a,b$ 均为正整数。

• 2 为查询操作。表示询问此时结束学习的期望时间是多少。对 $10^9+7$ 取模。

输出格式

对于每个询问，输出一行一个整数表示答案。

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

提示

本题使用捆绑测试。

Subtask 编号	$n$	$m$	$k$	特殊性质	分值
$0$	$\le 300$			无	$11$
$1$	$\le 3000$				$4$
$2$	$\le 10^5$	$\le 10^5$	$\le 1$	B	$5$
$3$				无	$14$
$4$		$=0$	$\le 10^5$		$19$
$5$		$\le 10^5$		A
$6$				B	$8$
$7$				C	$10$
$8$				无

以下的“区间”均指 $[l_i,r_i]$。

特殊性质 A：保证对于 $\forall i \in [1,m]$，$r_i-l_i+1\le 5$。

特殊性质 B：保证这些区间两两的交 $\le 1$。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $r_i\le l_j$ 或 $r_j\le l_i$。

特殊性质 C：保证这些区间不存在包含关系。即对于 $\forall i,j \in [1,m]$ 且 $i\ne j$，有 $l_i>l_j$ 或 $r_i<r_j$。

对于 $100\%$ 的数据，$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$。