Civilization: The Game of Beliefs

This game, called Civilization (with a twist), is played on a network of cities and roads. There are n cities (numbered from 1 to n) and m bidirectional roads (numbered from 1 to m). The game involves three types of events:

1. Add People: The system adds N people to a given city X and assigns them a belief value C.
2. Cut Road: The system severs a road given by its road id.
3. Query Probability: The system asks, given a city X, if you select N people from all cities reachable from X (by road connections that have not been cut), what is the probability that all selected people have a belief equal to C? The answer should be computed modulo 19260817.

In a query, let the total number of people in the connected component be S and the number of people with belief C be T. If S $$\frac{\binom{T}{N}}{\binom{S}{N}} \mod 19260817,$$

where the binomial coefficient is defined as usual.

Note:

• The input data may contain self-loops and multiple roads between the same pair of cities.
• The same road may be cut more than once; only the first cut is effective.
• Since it is the princess's game, the input size may be large; please optimize your input operations.

inputFormat

The input begins with two integers n and m (the number of cities and roads).

The next m lines each contain two integers u and v, indicating that there is a bidirectional road connecting city u and city v. Roads are numbered from 1 to m in the order of appearance.

Then an integer Q is given, representing the number of events.

Each of the following Q lines represents an event in one of the following formats:

• For adding people: 1 X N C — add N people with belief C to city X.
• For cutting a road: 2 X — cut the road with id X.
• For a query: 3 X N C — from the connected component containing city X, if you randomly choose N people, what is the probability that all of them have belief C?

outputFormat

For each query event (event type 3), output one line containing a single integer: the required probability computed modulo 19260817.

sample

4 3
1 2
2 3
3 4
5
1 1 10 100
1 2 5 100
3 1 3 100
2 2
3 1 3 100

1
1

</p>