An Animal Contest 7 P6 - S-Squirrel?

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.5s
Memory limit: 256M

Problem types

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.


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



There are no comments at the moment.