Eggscavation

This problem is adapted from CCO 2015 Day2 T3 "Eggscavation".

You are on vacation in the island nation of Cartesia, famous for its picturesque square beaches. The beach is organized as an N × N grid. You brought your trusty shovel and plan to excavate a square submatrix of size K × K (with the requirement that the entire submatrix must lie within the beach).

Under the island, there are M different types of undiscovered seashells. For each shell species i, there are S_i shells hidden at distinct positions. When you excavate a submatrix, for each species present in that region you collect one shell which you can sell for 1 dollar each (multiple shells of the same species do not provide extra revenue).

The complication arises because a flamboyant dodo bird scampers around the beach, and at any given moment it may deposit an egg on any grid cell (even if there is already an egg or a seashell on that cell). If the K × K submatrix you dig contains even a single egg, the scientist who would have bought your shells gets alarmed by the presence of the endangered species’ egg, and you end up with zero revenue for that excavation.

Your task is to compute the probability that a randomly chosen K × K excavation (chosen uniformly from all valid positions) will yield a positive revenue (i.e. you collect at least one seashell and encounter no egg in the excavated submatrix).

The probability should be computed as follows:

Probability = (number of valid K × K submatrices) / ((N - K + 1)²).

Note: A submatrix is valid if it does not contain any egg and contains at least one seashell (of any species).

inputFormat

The input begins with a line containing four integers N, K, M, and E where:

• N (1 ≤ N ≤ 1000) is the size of the square beach.
• K (1 ≤ K ≤ N) is the side length of the submatrix to excavate.
• M (1 ≤ M ≤ 100) is the number of seashell species.
• E (0 ≤ E ≤ 10⁵) is the number of eggs deposited by the dodo bird.

This is followed by M blocks. Each block describes one type of seashell. The first line of a block contains an integer S_i (the number of shells of that species, 1 ≤ S_i ≤ 10⁵). It is followed by S_i pairs of integers representing the 1-indexed row and column positions where that shell is hidden. (Note: Positions for a given species are distinct; however, different species may appear in the same cell.)

After the seashell information, there are E lines. Each line contains two integers representing the 1-indexed row and column positions of an egg.

You may assume that all positions are within the bounds of the beach.

outputFormat

Output a single line containing the probability that a randomly chosen K × K submatrix (excavation plan) yields a positive revenue. The answer should be printed as a floating-point number. Answers within an absolute or relative error of 10^-6 will be accepted.

sample

3 2 1 1
1 1 1
3 3

0.25