红包是一个有拖延症的男孩子。

红包由于NOI惨挂心情不好，直到还剩下 $n$ 周的时候他才开始写作业。

由于红包会 “时间静止” 大法，所以红包的一周有 $m$ 天。

现在他把这 $n\times m$ 天排成 $n$ 行 $m$ 列的日历开始计划每天要写的作业量。

初始时每天要做的作业量都是 $0$。

接下来，红包会有 $q$ 个行为，每次都会选择一个红包的形状，把红包内的每一天的作业量增加一个奇怪的组合数。

详细地说，每个行为可以用 $v,u,k$ 表示：对所有的 $i,j$，若满足 $0\le i\le j$ 且 $j\ge k$ 则将第 $v+i$ 周第 $u-i+j$ 天的作业量增加 $(\genfrac{}{}{0ex}{}{j}{i})$，即 $j$ 个里面选 $i$ 个的方案数（如果不存在这一天则不执行）。

在所有行为结束后，红包就计划好了每天要做的作业量。

虽然能不能完成是另一回事，但是现在请帮红包算出每天计划要做的作业量。

输入格式

由于本题输入数据很大，所以采取在程序内生成数据的方式。

有一个随机数产生器，有个内部变量 $x$ 初始时为 $x_0$，每次产生随机数时它会将 $x$ 变为 $(100000005x+20150823)mod998244353$，然后返回 $\lfloor \frac{x}{100}\rfloor$。（$amodb$ 表示 $a$ 除以 $b$ 的余数，该运算的优先级高于加减法。$\lfloor \alpha \rfloor$ 表示 $\alpha$ 向下取整后的结果。）

输入文件共一行，包含四个整数 $n,m,q,x_0$。保证 $n,m,q\ge 1$，$0\le x_0<998244353$。

每次，你需要按顺序产生三个随机数 $\hat{v},\hat{u},\hat{k}$，然后令 $v=\hat{v}modn+1$，$u=\hat{u}modm+1$，$k=\hat{k}mod(n+m-v-u+1)$，表示一个行为。你需要重复该过程 $q$ 次来获得所有行为的参数。

输出格式

共 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数表示第 $i$ 周第 $j$ 天要做的作业量。你只用输出答案对 $998244353$ 取模后的结果。

样例一

input

3 2 2 1234

output

0 0
1 1
1 4

explanation

两次操作分别为：$(2,1,2)$ 和 $(2,1,0)$。

样例二

input

10 10 20 5678

output

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 6 7
0 0 0 0 0 0 0 16 22 30
0 0 0 0 1 1 26 42 72 104
0 1 2 3 4 30 56 126 198 1227
0 1 4 7 27 58 170 296 1293 4522
0 1 5 18 48 176 346 1153 5449 9971
0 1 7 28 133 309 895 5480 10929 20908

限制与约定

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载