Minefield Probability Queries

You have won your very own island—but it comes with a dangerous legacy: an unexploded minefield! The minefield is an m × n grid. Each square may contain 0 or 1 mine. The engineers who deployed the mines did so independently with a preselected probability for each square, but they only recorded the probabilities and the total number of mines, t, deployed in the entire grid.

Your task is to answer several queries. In each query you are given a rectangular subset of the grid, and you must compute the conditional probability distribution for the number of mines in that subset, given that the total number of mines in the entire grid is exactly t.

More formally, let p_ij be the probability that a mine was placed in cell (i,j). The engineers deployed mines independently, so the unconditioned probability of any configuration is the product over cells of p_ij (if a mine is present) or 1-p_ij (if not). However, you know that exactly t mines were deployed. For a given query defining a subset S of cells, compute for every k = 0,1,…,|S| the probability that exactly k mines are present in S, conditioned on the entire grid having exactly t mines.

Note: Any formulas should use LaTeX notation. For example, the conditional probability for exactly k mines in S is given by:

$$P(k \mid t) = \frac{[x^t] \left(G_S(x) \cdot G_{\bar{S}}(x)\right) \text{ with the term for } k \text{ mines in } S}{[x^t] \left(\prod_{(i,j)} ((1-p_{ij})+p_{ij}x)\right)} $$

where \(G_S(x)=\prod_{(i,j)\in S}((1-p_{ij})+p_{ij}x)\) and \(G_{\bar{S}}(x)\) is defined similarly for the complement of \(S\).

inputFormat

The first line contains four numbers: m, n, t, and q where:

• m and n are the dimensions of the grid.
• t is the total number of mines deployed in the grid.
• q is the number of queries.

The next m lines each contain n floating point numbers. The j-th number in the i-th line is p_ij, the independent probability that cell (i,j) was mined.

Each of the following q lines contains four integers: r1 c1 r2 c2, representing the top‐left and bottom‐right coordinates (1-indexed) of a rectangular query region.

outputFormat

For each query, output one line with |S|+1 floating point numbers, where |S| is the number of cells in the queried rectangle. The k-th number (0-indexed) should be the probability (with at least 6 decimal places of precision) that the query region contains exactly k mines, conditioned on the entire grid having exactly t mines.

sample

2 2 1 2
0.5 0.5
0.5 0.5
1 1 1 1
1 1 2 2

0.750000 0.250000
0.000000 1.000000 0.000000 0.000000 0.000000

</p>