Eggscavation

You are taking a vacation. Writing C shell scripts got old, so you have decided to collect seashells instead.

The island nation of Cartesia has a square beach made of an $N \times N$ grid of square cells. Your shovel scoops up one $K \times K$ square subgrid of the beach, and that subgrid must lie entirely inside the beach, so there are exactly $(N - K + 1)^2$ places where you can dig.

There are $M$ undiscovered species of shells buried under the cells. Species $i$ has $S_i$ shells, one in each of $S_i$ grid cells, with $1 \le S_i \le 4$. A scientist back home pays you one dollar for every distinct species you bring back. Extra shells of a species you already have are worth nothing, so the profit of a scoop is the number of species that have at least one shell inside the dug subgrid.

A dodo bird runs around the beach. Every so often it buries an egg in a grid cell, including cells that already hold eggs or shells. If the $K \times K$ subgrid you dig contains at least one dodo egg, the scientists get angry that you are harming an endangered species and nobody pays you anything, so that scoop has a profit of 0 dollars.

At several points in time you want the probability that a scoop, chosen uniformly at random among all the places where you can dig, earns a profit of at least a given amount.

The first line contains two integers $N$ and $K$, the size of the beach and the size of the shovel ($1 \le N \le 2500$, $1 \le K \le N$).

The second line contains the integer $M$, the number of species of shells ($0 \le M \le 10^5$). Each of the next $M$ lines describes one species. Line $i$ starts with the integer $S_i$ ($1 \le S_i \le 4$) and continues with $2 \times S_i$ more integers, the cells between $(1, 1)$ and $(N, N)$ where the $S_i$ shells of that species are buried. Cell $(r, c)$ is the cell in row $r$ and column $c$.

The next line contains $T$ ($1 \le T \le 10\,000$). Each of the next $T$ lines is one point in time, given from oldest to newest, in one of these two forms:

• 1 A B: the dodo just buried an egg in cell $(A, B)$ ($1 \le A, B \le N$).
• 2 V: report the probability that a random dig at this moment has a profit of at least $V$ dollars ($1 \le V \le 10^9$). Computing this probability removes nothing and adds nothing, so the shells and the eggs stay where they are.

For each 2 V line, print on its own line the probability that a random scoop earns a profit of at least $V$ dollars.

Print the probability rounded to exactly five digits after the decimal point, and round up when the sixth digit is 5 or more. A probability of $8/9$ prints as 0.88889, a probability of 0 prints as 0.00000, and a probability of 1 prints as 1.00000.