题目描述

你可能已经赢了！实际上，你确实已经赢了！你赢得了只属于你的小岛，这座岛位于未被探索过的大洋的最深处！或者说，大部分未被探索过。恰恰这时，在你的面前出现了一支小型军队。当他们打包好行李飞走的时候，他们留下了各种各样的废料，弹药，管道，……和未被探索过的防御性军械。那就对了：你拥有了只属于你的雷区。

雷区由一个 $m\times n$ 大小的网格组成，网格中的每个单元格有 $0$ 或 $1$ 个地雷。幸运的是，你能够从工程师放置地雷时的操作中复原工程师安装地雷的计划。不幸的是，地雷的确切位置从未被记录下来：对于每个单元格，工程师都有一个预先选取且独立的概率在此安放地雷。然而，你知道总共安放了多少地雷。

你想估计你的岛上的某些部分有多么安全。写一个程序计算一些雷区单元格集合中包含的每种地雷总数的概率。

输入格式

第一行包含四个整数 $m,n,t,q$，$m$ 和 $n\ (1\le m,n\le 500)$ 表示雷区的大小，$t\ (0\le t\le mn)$ 表示地雷的总数，$q\ (0\le q\le 500)$ 表示询问的次数。

第二行包含 $m$ 个实数 $p_1,p_2,\ldots,p_m$（对于所有 $i$，满足 $0\le p_i\le 0.1$，小数点后最多六位），第三行包含 $n$ 个实数 $q_1,q_2,\ldots,q_n$（对于所有 $j$，满足 $0\le q_j\le 0.1$，小数点后最多六位）。对于单元格 $(i,j)$，工程师预先选出在此放置地雷的概率为 $p_i+q_j$。在一个单元格中放置地雷与否是互相独立的，放置恰好 $t$ 个地雷的概率至少为 $10^{-5}$。

接下来 $q$ 行，每行描述一个询问。每行开头有一个整数 $s\ (0\le s\le 500)$，接着有 $s$ 对整数 $i,j\ (1\le i\le m,1\le j\le n)$，表示网格中 $s$ 个不同的单元格的坐标。

输出格式

对于每个对 $s$ 个单元格的询问，输出 $s+1$ 个实数，表示给定的 $s$ 个单元格中一共有 $0,1,2,\ldots,s$ 个地雷的概率。你的答案与标准答案之间的绝对误差最多为 $10^{-6}$。

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

0.75 0.25
0.5 0.5 0

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

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