大力水手问禅师：“大师，我觉得我光有力气是不够的。比如我吃菠菜可以让力气更大，但是却没有提升跑步的速度。请问怎样才能跑得更快？我试过吃白菜，没有效果。”

禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这道UOJ Round的C题。”

令 $p=998244353$（$7\times 17\times 2^{23}+1$，一个质数）。

给你整数 $n,c,d$。现在有整数 $x_1,\dots ,x_n$ 和 $b_1,\dots ,b_n$ 满足 $0\le x_1,\dots ,x_n,b_1,\dots ,b_n<p$，且对于 $1\le i\le n$ 满足：

$$\sum _{j=1}^{n}gcd(i,j{)}^c\cdot \mathrm{lcm}(i,j{)}^d\cdot x_j\equiv b_i(\mathrm{mod}p)$$ 其中 $v\equiv u(\mathrm{mod}p)$ 表示 $v$ 和 $u$ 除以 $p$ 的余数相等。$gcd(i,j)$ 表示 $i$ 和 $j$ 的最大公约数，$\mathrm{lcm}(i,j)$ 表示 $i$ 和 $j$ 的最小公倍数。

有 $q$ 个询问，每次给出 $b_1,\dots ,b_n$，请你解出 $x_1,\dots ,x_n$ 的值。

输入格式

第一行四个整数 $n,c,d,q$。保证 $n,q\ge 1$。

接下来 $q$ 行，每行 $n$ 个整数依次表示 $b_1,\dots ,b_n$。保证 $0\le b_1,\dots ,b_n<p$。

输出格式

共 $q$ 行，每行对给出的 $b_1,\dots ,b_n$，输出对应的 $x_1,\dots ,x_n$。如果有多组解输出任意一组即可。如果无解那么这一行只用输出一个整数 $-1$。

样例一

input

3 1 0 2
1 0 0
1 2 3

output

499122179 998244352 499122176
998244352 1 1

explanation

对于第一个询问，要满足的等式为：

$$\begin{array}{r}\{\begin{array}{llll}{x}_1+x_2+x_3& \equiv & 1& (\mathrm{mod}p)\\ x_1+2x_2+x_3& \equiv & 0& (\mathrm{mod}p)\\ x_1+x_2+3x_3& \equiv & 0& (\mathrm{mod}p)\end{array}\end{array}$$

样例二

见样例数据下载。

限制与约定

对于所有数据，$nq\le 3\times {10}^5$，$0\le c,d\le {10}^9$。

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

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

后记

还没听完题，大力水手就嘶吼着：“太难了我不会我不会！”，飞快地跑掉了。

禅师看着大力水手消失的背影，叹了口气说：“你们这些人啊，每天就想做些大水题，一碰到难题，跑得不知道比谁都快。”

后来大力水手把UOJ Round的C题题面贴在了汽车的后挡风玻璃上，人类从此掌握了光速旅行的正确方式。

下载

样例数据下载