Problem F
Mid Card

Sen and Yubaba

The witch Yubaba has forced Sen to play a card game to when back her and her parents’ freedom. Cards range from $1$ to $C$. Sen has an infinite number of cards for each possible value. In this game, there are $N$ rounds. Within each round $i$, Sen can win by playing a card between range $L_i$ and $H_i$ (inclusive).

Please help Sen resolve $T$ operations:

Operation type $0$ is a query of the form $0$ $A$ $B$ $K$. In this operation, Sen enters the card game starting from round $A$ and exits the card game after round $B$. Yubaba has allowed Sen to choose exactly $K \: (1 \leq K \leq \min (100, R-L+1))$ rounds $(R_1, R_2, \dotsc , R_K)$ in this range where $(A \leq R_1 < R_2 \dotsc < R_K \leq B)$. She then plays exactly $K$ cards $(C_1, C_2, \dotsc , C_K)$ where $(1 \leq C_i \leq C)$ such that $C_i$ is played during round $R_i$. Note that card values can be repeated between rounds because she has infinitely many cards of each value. To answer the query, output how many distinct tuples $(R_1, R_2, \dotsc , R_K, C_1, C_2, \dotsc , C_K)$ exist so that Sen wins every round that she enters. Given that this number can be large, please answer modulo $10^9+7$.

Operation type $1$ is an update of the form $1$ $P$ $S$ $T$. In this operation, Yubaba changes the rules of the card game. Now, for round $P$, Sen has to play a card between $S$ and $T$ to win. This update applies for all future operations.

Input

The first line of input contain three space-separated integers $N \: (1 \leq N \leq 100\, 000)$, $C \: (1 \leq C \leq 10\, 000)$, and $T \: (1 \leq T \leq 5\, 000)$, which represent the number of rounds, the max possible value of a card, and the number of operations respectively.
The next $N$ lines of input contain a list of two space-separated integers that correspond to the $L_i$ and $H_i \: (1 \leq L_i \leq H_i \leq C)$ of round $i$ at the start of the game. $L_i$ and $H_i$ correspond respectively to the lowest and highest cards that Sen can play to win round $i$ originally before any updates.
The next $T$ lines of input contain operations. Each line will begin with a $0$ or a $1$.

• If a line starts with a $0$, it will contain three additional space-separated integers $A$, $B \: (1\leq A \leq B \leq N)$, and $K \: (1 \leq K \leq \min (100, B-A+1))$. $A$ and $B$ corresponds to the first round and last rounds Sen can play in for that query, while $K$ corresponds to the number of rounds she plays in for that query

• If a line starts with a $1$, it will contain three additional space separated integers $P \: (1 \leq P \leq N)$, $S$, and $T \: (1 \leq S \leq T \leq C)$. $P$ corresponds to the round being updated and $S$ and $T$ correspond to the new lowest and highest cards Sen must play to win round $P$.

Output

For each query of type $0$, please output the number of distinct tuples $(R_1, R_2, \dotsc , R_K, C_1, C_2, \dotsc , C_K)$ that follow the restrictions listed in the query, modulo $10^9+7$

Sample Explanation

In the sample case, for the first query, she has five ways to win by playing only in round $1$, seven ways to win by playing only in round $2$, four ways to win by playing only in round $3$, and four ways to win by playing only in round $4$. Thus, the answer to the first query is $20$. For the second query, she must choose to play in rounds two and three. To win both these rounds, there are $7 \cdot 4 = 28$ possible tuples of rounds and winning cards for the second query.

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

20
28
14
4