千寻与汤婆婆

魔女汤婆婆强迫千寻玩一个卡牌游戏，以赢回她和她父母的自由。卡牌的数值范围为 $1$ 到 $C$。千寻对于每种可能的数值都有无限张卡牌。在这个游戏中，一共有 $N$ 轮。在第 $i$ 轮中，千寻只要打出一张数值在 $[L_i, H_i]$ 范围（闭区间）内的卡牌即可获胜。

请帮助千寻处理 $T$ 个操作：

操作类型 0 是格式为 0 A B K 的查询。在该操作中，千寻从第 $A$ 轮开始进入卡牌游戏，并在第 $B$ 轮结束后退出。汤婆婆允许千寻在此范围内恰好选择 $K$（$1 \le K \le \min(100, B - A + 1)$）轮 $(R_1, R_2, \dots, R_K)$，满足 $A \le R_1 < R_2 < \dots < R_K \le B$。然后她恰好打出 $K$ 张卡牌 $(C_1, C_2, \dots, C_K)$（$1 \le C_i \le C$），其中 $C_i$ 在第 $R_i$ 轮打出。注意，由于她每种数值的卡牌都有无限张，因此不同轮次中打出的卡牌数值可以重复。为了回答该查询，请输出有多少个不同的元组 $(R_1, R_2, \dots, R_K, C_1, C_2, \dots, C_K)$，使得千寻在她参与的每一轮中都能获胜。由于这个数量可能很大，请对 $10^9 + 7$ 取模后输出。

操作类型 1 是格式为 1 P S T 的修改。在该操作中，汤婆婆改变了卡牌游戏的规则。现在，对于第 $P$ 轮，千寻必须打出一张在 $S$ 到 $T$ 之间的卡牌才能获胜。此修改适用于所有后续操作。

输入格式

输入的第一行包含三个空格分隔的整数 $N$（$1 \le N \le 100\,000$）、$C$（$1 \le C \le 10\,000$）和 $T$（$1 \le T \le 5\,000$），分别代表轮数、卡牌的最大可能数值以及操作次数。

接下来的 $N$ 行输入，每行包含两个空格分隔的整数，对应游戏开始时第 $i$ 轮的 $L_i$ 和 $H_i$（$1 \le L_i \le H_i \le C$）。$L_i$ 和 $H_i$ 分别对应在进行任何修改之前，千寻在第 $i$ 轮中获胜原本可以打出的最低和最高卡牌数值。

接下来的 $T$ 行输入包含操作。每行将以 0 或 1 开头。

• 如果某行以 0 开头，它将包含另外三个空格分隔的整数 $A, B$（$1 \le A \le B \le N$）和 $K$（$1 \le K \le \min(100, B - A + 1)$）。$A$ 和 $B$ 对应千寻在该查询中可以参与的第一轮和最后一轮，而 $K$ 对应她在该查询中参与的轮数。
• 如果某行以 1 开头，它将包含另外三个空格分隔的整数 $P$（$1 \le P \le N$）、$S$ 和 $T$（$1 \le S \le T \le C$）。$P$ 对应被修改的轮次，$S$ 和 $T$ 对应千寻在第 $P$ 轮获胜必须打出的新最低和最高卡牌数值。

输出格式

对于每个类型为 0 的查询，请输出满足查询中列出的限制的不同元组 $(R_1, R_2, \dots, R_K, C_1, C_2, \dots, C_K)$ 的数量，对 $10^9 + 7$ 取模。

样例

输入样例 1

4 9 6
1 5
2 8
6 9
1 4
0 1 4 1
0 2 3 2
1 2 4 4
1 1 2 6
0 1 4 1
0 2 3 2

输出样例 1

20
28
14
4

说明

在样例中： 对于第一个查询（0 1 4 1），她仅在第 1 轮玩有 5 种获胜方式，仅在第 2 轮玩有 7 种获胜方式，仅在第 3 轮玩有 4 种获胜方式，仅在第 4 轮玩有 4 种获胜方式。因此，第一个查询的答案是 $5 + 7 + 4 + 4 = 20$。

对于第二个查询（0 2 3 2），她必须选择在第 2 轮和第 3 轮玩。为了在这两轮中都获胜，有 $7 \times 4 = 28$ 种可能的轮次和获胜卡牌元组。