Description

考虑如下问题：

长为 $n$ 的数轴上，坐标 $i$（$0\leq i<n$）有 $a_i$ 个黑球，$m-a_i$ 个白球，任意两个球都是可区分的。

对于一个 $0\sim n-2$ 的排列 $p$，按顺序遍历所有 $i$（$0\leq i<n-1$），执行如下操作：

• 在坐标 $p_i,p_i+1$ 上分别选择球 $x,y$，将球 $x$ 的颜色改为球 $y$ 的颜色。

求在所有 $(n-1)!m^{2(n-1)}$ 情况下结束时数轴上黑球的个数和。

现在给定 $n,m,k$ 和初始序列 $a_0,a_1,\ldots ,a_{n-1}$。保证 $n$ 是 $2$ 的幂。令 $f(a)$ 表示序列 $a_0,a_1,\ldots ,a_{n-1}$ 关于上述问题的答案。

执行 $i$（$0\le i < k$）次操作，每次交换序列中相邻两个元素，求对于所有 $(n-1)^i$ 种可能的操作，操作后，$f(a)$ 的和对 $998244353$ 取模。

Input

第一行包含三个正整数 $n,m,k$（$2\le k\le n\le 2^{17}$，$2\le m < 998244353$，保证 $n$ 为 $2$ 的幂）。

第二行包含 $n$ 个整数 $a_0,a_1,\ldots,a_{n-1}$（$1\le a_i \le m$）。

Output

输出 $k$ 行每行一个整数，第 $i$ 行表示操作 $i-1$ 次的答案。

Samples

2 2 2
1 2

14
10

Resources

The 23rd UESTC Programming Contest Final