ICPC 2020 · Problem L · Sweep Stakes

Time limit: 20 seconds

You may have already won! In fact, you did already win! You won your very own island, in the deepest reaches of the unexplored ocean! Well, mostly unexplored. As it happens, there was a small military base there before you, and when they packed up and flew out they left behind an assortment of scraps, munitions, tunnels, . . . and unexploded defensive ordnance. That’s right: You now possess your very own minefield.

The minefield consists of an $m\times n$ grid, with any square of the grid holding 0 or 1 mines. Fortunately, you were able to recover the engineers’ plans from when they deployed the mines. Unfortunately, the exact locations of the mines were never written down: the engineers had a preselected independent probability of deploying a mine in each square. However, you do know how many mines were placed in total.

You would like to estimate how safe various parts of your island are. Write a program to compute the probability of mine counts over various subsets of the minefield.

Input

The first line of input contains four integers $m$, $n$, $t$, and $q$, where $m$ and $n$ ($1 \le m, n \le 500$) are the dimensions of the minefield, $t$ ($0 \le t \le mn$) is the total number of mines, and $q$ ($0 \le q \le 500$) is the number of queries. The second line contains $m$ real numbers $p_{1}, p_{2}, . . . , p_{m}$ ($0 \le pi \le 0.1$ for all $i$, with at most six digits after the decimal point specified), and the third line contains $n$ real numbers $q_{1}, q_{2}, . . . , q_{n}$ ($0 \le qj \le 0.1$ for all $j$, with at most six digits after the decimal point specified). The preselected probability of the engineers placing a mine on square $(i, j)$ is $pi+qj$. All choices of whether to place a mine on a given square were made independently, and the value of $t$ is chosen so that the probability of deploying exactly $t$ mines is at least $10^{- 5}$.

Each of the remaining $q$ lines describes a single query. Each of those lines begins with an integer $s$ ($0 \le s \le 500$), followed by $s$ pairs of integers $i$ and $j$ ($1 \le i \le m$, $1 \le j \le n$), which are the coordinates of $s$ distinct squares in the grid.

Output

For each query with $s$ squares, output $s+ 1$ real numbers, which are the probabilities of the $s$ given squares containing $0,1, . . . , s$ mines. Your answer should have an absolute error of at most $10^{- 6}$.

Sample Input 1

2 2 1 2
0.05 0.05
0.05 0.05
1 1 1
2 2 1 1 2

Sample Output 1

0.75 0.25
0.5 0.5 0

ICPC World Finals 2020 Problem L: Sweep Stakes

Sample Input 2

3 4 3 4
0.02 0.04 0.06
0.005 0.07 0.035 0.09
1 3 2
3 1 4 2 4 3 4
4 1 2 2 3 3 1 1 4
8 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3

Sample Output 2

0.649469772 0.350530228
0.219607636 0.527423751 0.237646792 0.015321822
0.267615440 0.516222318 0.201611812 0.014550429 0
0.054047935 0.364731941 0.461044157 0.120175967 0 0 0 0 0

ICPC World Finals 2020 Problem L: Sweep Stakes