# 病毒狙击手

- 参考时间限制：1.0 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

尤里准备测试游戏中病毒狙击手的新弹头。实验员先在试验场的若干矩形区域增加初始强度，再隔离一块小区域，观察其中的传播过程。

每次试验都从同一份初始记录重新开始。尤里想看很久以后的结果，而下一次选择哪个区域，还取决于上一次的输出。

## 形式化问题描述

试验场有 $A$ 行、$B$ 列，初始强度均为 $0$ .先进行 $Q$ 次矩形增量操作：将左上角为 $(x_1,y_1)$ 、右下角为 $(x_2,y_2)$ 的闭矩形内每格强度加上整数 $C$ .这些操作期间不发生传播。

每次试验隔离一个 $N$ 行、$M$ 列的区域，将区域内格子按从上到下、每行从左到右编号为 $1$ 到 $d=NM$ .概率由区域内的相对编号决定，各次试验共用同一组概率。

对于来源格 $i$ ，给定五个概率 $p_{ij}=a_{ij}/b_{ij}$ ，依次对应自身、上、下、左、右。每一个整数时刻，针对每个仍在隔离区域内的目标方向，以对应概率发生一次传播：在下一时刻向目标格增加来源格在当前时刻的全部强度。所有传播同时结算，原有强度保留；本次新增强度从下一步起才参与传播。越界方向被忽略，输入仍须读取。各次传播试验彼此独立，五个概率的和不要求等于 $1$ .

有 $K$ 次询问，每次给出一个非负整数时刻 $T$ ，求隔离区域中各格在时刻 $T$ 的期望强度。每次均从矩形增量操作完成后的初值开始，不继承上一场试验的状态。

令 $P=1000000009$ .期望是分母不被 $P$ 整除的有理数。若期望写成 $r/s$ ，输出满足 $zs\equiv r\pmod P$ 且 $0\le z<P$ 的整数 $z$ .

第一场试验左上角为 $(1,1)$ .将本次输出的 $d$ 个整数按普通整数求和，记为 $S$ ，求和后不再对 $P$ 取模。下一场的左上角为

$$x=1+(S\bmod(A-N+1)),\qquad y=1+((7S)\bmod(B-M+1))$$

即先把每格期望转换成模 $P$ 的输出值，再用这些输出值的整数总和选取下一个区域。

## 输入格式

第一行包含六个整数 $A,B,N,M,Q,K$ .

接下来 $Q$ 行，每行包含五个整数 $x_1,y_1,x_2,y_2,C$ .

接下来 $d$ 行，第 $i$ 行依次包含 $a_{i0},b_{i0},a_{i1},b_{i1},\ldots,a_{i4},b_{i4}$ ，方向顺序为自身、上、下、左、右。

接下来 $K$ 行，每行包含一个十进制非负整数 $T$ ，无多余前导零。

## 输出格式

输出 $K$ 行，每行 $d$ 个整数，按区域内编号顺序给出本次询问的结果。

## 样例 1

### 输入

```text
1 2 1 2 2 3
1 1 1 1 5
1 2 1 2 2
0 1 0 1 0 1 0 1 1 1
0 1 0 1 0 1 1 1 0 1
0
1
2
```

### 输出

```text
5 2
7 7
14 14
```

### 解释

两个格子每步都向对方传播，原强度仍保留，因此从 $(5,2)$ 变为 $(7,7)$ ，再变为 $(14,14)$ .每次询问都重新从 $(5,2)$ 开始。

## 样例 2

### 输入

```text
1 2 1 2 1 1
1 1 1 1 1
0 1 0 1 0 1 0 1 1 1
0 1 0 1 0 1 0 1 0 1
1000000008
```

### 输出

```text
1 1000000008
```

### 解释

第一个格子的强度始终为 $1$ ，第二个格子每步增加 $1$ ，所以时刻 $T$ 的结果为 $(1,T\bmod P)$ .

## 样例 3

### 输入

```text
3 3 1 2 3 2
1 1 1 2 1000000000
2 1 2 2 7
3 1 3 2 11
0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1
0
0
```

### 输出

```text
1000000000 1000000000
11 11
```

### 解释

第一次输出之和为 $2000000000$ ，下一块区域的左上角是 $(3,1)$ ，所以输出两个 $11$ .求和后若再次对 $P$ 取模，就会错误地选择另一个区域。


## 数据范围与保证

- $1\le N\le A\le1000$ ，$1\le M\le B\le1000$ ，$1\le d=NM\le50$ .
- $1\le Q\le10^6$ ，$1\le K\le5$ ，$0\le C\le10^9$ .
- $1\le x_1\le x_2\le A$ ，$1\le y_1\le y_2\le B$ .
- $0\le a_{ij}\le b_{ij}\le10^9$ ，$b_{ij}\ge1$ .
- $0\le T\le10^{1000}$ ；所有输入量均为整数。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $A=N$ ，$B=M$ ，$T\le1000$ ，$Q\le1000$ |
| 10% | $A=N$ ，$B=M$ ，$T=0$ |
| 20% | $A=N$ ，$B=M$ ，$T\le10^{18}$ |
| 30% | $T\le10^{18}$ |
| 10% | 无额外条件 |