题目描述

JOHNKRAM 最近在学习走迷宫。他现在进入了一个环形迷宫，里面有 $n$ 个点，编号为 $0 \sim n - 1$，点 $i$ 和点 $(i + 1) \bmod n$ 之间有道路。在 $0$ 时刻，JOHNKRAM 在点 $0$。JOHNKRAM 需要在 $T$ 秒内逃出去。

JOHNKRAM 有 $m$ 种行走方式，第 $i$ 种行走方式会顺时针移动 $a$ 个点，耗时 $1$ 秒。迷宫中有一个传送门，每 $x$ 秒打开一次，在 $0$ 时刻传送门是打开的。在 $i$ 秒时，传送门有 $\binom{T}{i}$ 种方式将 JOHNKRAM 送到终点。

JOHNKRAM 并不知道传送门在哪个点上，所以对于每一个点，他希望你能计算出传送门在这个点上时他在 $T$ 秒之内逃出去的方案数。答案可能很大，你只需要告诉他答案 $\mathop{\text{mod}} 998244353$ 的结果即可。

输入格式

第一行四个整数 $n, m, T$ 和 $x$，意义如题所示。
接下来 $m$ 行，每行一个整数 $a_i$，意义如题所示。

输出格式

一行 $n$ 个整数，表示传送门在每个点上时的答案。

样例

4 3 5 1
1
2
3

256 256 256 256

数据范围与提示

对于 $20\%$ 的数据，$n \leq 10$；
对于 $40\%$ 的数据，$n, m \leq 500$；
对于 $100\%$ 的数据，$1\leq n,m \leq 2^{16}; n$ 是 $2$ 的整数次幂 $; T \leq 10^9; x = 1,2,4,7,8$。