题目描述

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 $ 个整数，表示传送门在每个点上时的答案。

样例

input

4 3 5 1
1
2
3

output

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 $。