病毒狙击手¶

参考时间限制：1.0 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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¶

输入¶

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

输出¶

5 2
7 7
14 14

解释¶

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

样例 2¶

输入¶

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

输出¶

1 1000000008

解释¶

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

样例 3¶

输入¶

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

输出¶

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%	无额外条件