Description

This problem is translated from CCO 2015 Day 2 T3 “Eggscavation”.

Vacation time has arrived. You are tired of C shell (a programming language), so you decide to collect seashells (“Seashell”, a homophone of “C Shell”).

You decide to visit the island nation of Cartesia for a vacation. The island is famous for its beautiful square beach. The beach is divided into an $N \times N$ grid. You bring your trusty shovel, and you can dig out a square submatrix of size at most $K \times K$ on the island. To ensure your shovel is reliable, the $K \times K$ area you dig must lie entirely within the beach.

Under the island, there are $M$ unexplored species of shells. Specifically, for each species $i$, there are $S_i$ shells at distinct positions. For each different species of shell, you dig it up, take it home, and sell it to a scientist for $1$ dollar each. Multiple shells of the same species have no extra value.

Unfortunately, a fancy dodo bird runs around on the beach. At a given moment, it may bury an egg in a grid cell, including cells that already have an egg or shells. The bad news is: if the $K \times K$ square submatrix you dig contains a dodo egg, the scientist will get very upset because you are harming an endangered species, and nobody will pay you.

After thinking about this, you decide to sit down and write a program to simulate the excavation. You need to compute the probability of your excavation outcomes: when you choose a digging plan uniformly at random at different times, what is the probability that you can earn at least some amount to repay your student loans? Nobody wants to work for nothing.

Input Format

The first line contains two integers $N, K$, representing the size of the island and the shovel.

The second line contains an integer $M$, the number of shell species. The next $M$ lines each describe a species $i$: they contain an integer $S_i$, followed by $2 \times S_i$ numbers representing coordinates between $(1,1)$ and $(N,N)$, indicating the positions where the $S_i$ shells are buried.

Then there are $T$ lines, each representing a time point, sorted from the farthest time to the most recent. Each line is in one of the following formats:

• $1$ $A_i$ $B_i$, meaning the dodo lays an egg at $(A_i, B_i)$.
• $2$ $V_i$, meaning we want to compute the probability that a random excavation at this time point yields profit $\ge V_i$. Note that shells and eggs are not actually dug up during these computations.

Output Format

For each query, output one line giving the probability that a random excavation yields at least the specified profit. The absolute error between your answer and the standard answer must not exceed $10^{-4}$.

4 2
3
3 1 1 2 3 4 2
3 1 4 2 3 3 2
4 2 1 2 4 4 1 4 4
6
2 2
2 3
1 2 3
2 2
2 3
2 4

0.88889
0.33333
0.44444
0.11111
0.00000

Hint

[Sample Explanation.]

Initially, the shells are arranged as shown below:

We will dig at most a $2 \times 2$ area, so there are $9$ possible excavations. When there are no eggs, $8$ excavations contain at least two species of shells, and $3$ excavations contain three species of shells.

An egg falls into the cell that contains shells $1$ and $2$.

In this case, $\frac{4}{9}$ of the excavations contain at least two species of shells and no egg. Only one excavation contains all species of shells and no egg: digging the bottom-left corner. The final output indicates that there is no excavation that contains four species of shells.

[Constraints.]

For at least $15\%$ of the testdata, $1 \le N \le 40$.

For another $25\%$ of the testdata, all update operations appear before any query operations.

For $100\%$ of the testdata, $1 \le K \le N \le 2500$, $0 \le M \le 10^5$, $1 \le S_i \le 4$, $0 \le T \le 10000$, $1 \le A_i, B_i \le N$, $1 \le V_i \le 10^9$.

Translated by ChatGPT 5