It is vacation time! You are tired of C shell (the programming language), so you decide to go collect seashells (which sounds like C shell).

You decide to visit the islands of Cartesia. The island is famous for its beautiful square beach. The beach is divided into an $N \times N$ matrix. You have brought your reliable shovel, and you can use it to dig at most one $K \times K$ square sub-matrix on the island. To ensure your shovel remains reliable, the $K \times K$ square sub-matrix you dig must be entirely within the beach.

Under the island, there are $M$ types of unexplored seashells. Specifically, for each seashell type $i$, there are $S_i$ seashells at different locations. For each distinct type of seashell you dig up, you take it home and sell it to a scientist for $1$ dollar each. Multiple seashells of the same type have no additional value.

The trouble is that a fancy dodo bird is running around on the beach. At any given moment, it might lay an egg in a grid cell, including cells that already contain eggs or other seashells. The bad news is that if the $K \times K$ square sub-matrix you dig up contains a dodo bird's egg, the scientist will be very upset because you are endangering an endangered species, and therefore no one will pay you any money.

Thinking about this, you decide to sit down and write a program to simulate the digging. You will calculate the probability of your digging, assuming that when you choose a digging plan at different time points with equal probability, you need to ensure at least one income value to pay off your student loans. Who wants to work for nothing?

Input

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

The second line contains a number $M$, representing the number of seashell types. The next $M$ lines each represent a type $i$, containing an integer $S_i$, followed by $2 \times S_i$ integers, which are coordinates between $(1, 1)$ and $(N, N)$, representing the locations where $S_i$ seashells are buried.

The next $T$ lines each represent a time point, sorted from furthest to nearest in time, and each line is in one of the following formats:

• $1\ A_i\ B_i$, indicating that the dodo bird laid an egg at $(A_i, B_i)$.
• $2\ V_i$, indicating that we want to calculate the probability of a random digging plan yielding a profit of at least $V_i$ at this time point. Note that neither seashells nor eggs are actually dug up during the calculation.

Output

For each query, output one line representing the probability of obtaining at least the specified profit from a random digging plan. The absolute difference between your answer and the standard answer must not exceed $10^{-4}$.

Examples

Input 1

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

Output 1

0.88889
0.33333
0.44444
0.11111
0.00000

Note

Initially, the arrangement of seashells is as follows:

We will use the shovel to dig a $2 \times 2$ grid, so we have $(N-K+1)^2 = 9$ possible digs.

When no eggs appear, 8 digs contain at least two types of seashells, and 3 digs contain three types of seashells.

An egg falls into the grid containing seashell 1, 2.

In this case, 4 of the digs contain at least two types of seashells and no eggs, and only one dig contains all types of seashells and no eggs, which is digging the bottom-left corner. The final output indicates that no dig contains four types of seashells.

Constraints

For $15\%$ of the data, $1 \le N \le 40$;

For another $25\%$ of the data, all update operations occur before the query operations;

For $100\%$ of the data, $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$.