你已经赢了！事实上，你确实赢了！你在未探索海洋的最深处赢得了属于你自己的岛屿！好吧，基本上是未探索的。碰巧的是，在你之前那里有一个小型军事基地，当他们收拾行装飞走时，留下了一堆废料、弹药、隧道……以及未爆炸的防御性军火。没错：你现在拥有属于你自己的雷区了。

雷区由一个 $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, \dots, p_m$ ($0 \le p_i \le 0.1$，对于所有 $i$，小数点后最多指定六位数字)，第三行包含 $n$ 个实数 $q_1, q_2, \dots, q_n$ ($0 \le q_j \le 0.1$，对于所有 $j$，小数点后最多指定六位数字)。工程师在方格 $(i, j)$ 放置地雷的预选概率为 $p_i + q_j$。所有关于是否在给定方格放置地雷的选择都是独立做出的，且 $t$ 的值使得部署恰好 $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, \dots, s$ 个地雷的概率。你的答案的绝对误差应不超过 $10^{-6}$。

样例

样例输入 1

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

样例输出 1

0.75 0.25
0.5 0.5 0

样例输入 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

样例输出 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