Just as the squirrel counterattack starts you wake up to the noise of your alarm clock ringing beside your bed. You feel sweat rolling down your back and trembling plagues your hands as a deep chill permeates throughout your body. What a weird dream!

To shake off the lingering aftereffects (you can't look at squirrels the same way anymore — they give off a threatening aura) you decide to visit your favourite competitive programming site (DMOJ of course) and join a contest from your favourite contest series (AAC of course) to do the last problem:

There are ~N~ multisets numbered from ~1~ to ~N~ that are all initially empty and a graph with ~M~ nodes initially with ~K~ edges. We define the value of the graph as the sum of the squares of the sizes of all of its connected components. You have to process ~Q~ queries in the form ~L_i~ ~R_i~ ~X_i~. There are ~2~ types of queries:

1. If ~1 \leq X_i \leq M~, an edge is added between node ~X_i~ and all the nodes present within the multisets numbered ~j~ where ~L_i \leq j \leq R_i~. Then, node ~X_i~ is added to all of these multisets. Output the value of the graph.

2. If ~X_i = 0~, output the expected value of the graph if a node was chosen uniformly at random and an edge was added between it and all of the nodes present within the multisets numbered ~j~ where ~L_i \leq j \leq R_i~. Afterwards, all of these multisets are cleared of nodes.

Constraints

~1 \leq N, M, Q \leq 5 \times 10^5~

~0 \leq K \leq 5 \times 10^5~

~1 \leq L_i \leq R_i \leq N~

~0 \leq X_i \leq M~

Subtask 1 [10%]

~1 \leq N, M, Q \leq 2 \times 10^3~

Subtask 2 [40%]

There will only be queries of type ~1~.

Subtask 3 [50%]

No additional constraints. This batch will only run if subtask ~1~ and subtask ~2~ are successfully completed.

Input Specification

The first line will contain four space separated integers ~N~, ~M~, ~Q~, ~K~.

The next ~K~ lines will contain two space separated integers ~u_i~, ~v_i~ representing an edge in the graph.

The next ~Q~ lines contain three space separated integers ~L_i~, ~R_i~, ~X_i~.

Output Specification

Output ~Q~ lines with the ~i~-th line containing one integer: the answer to the ~i~-th query.

For queries of type ~2~, output the expected value modulo ~10^9 + 7~. More specifically, if the expected value is ~\frac{x}{y}~, output ~xy^{-1} \pmod{10^9 + 7}~.

Sample Input

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

Sample Output

12
12
12
12
400000017
18
18
800000036
24
24