有 $n$ 个数 $a_1,a_2,\dots,a_n$ 。保证 $1\leq a_i\leq m$ 。

初始时有一个变量 $X=0$ 。你要进行 $k$ 轮操作，每次操作可以任意选择一个 $1\leq p\leq n$ 的 $p$ ，并将 $X$ 赋值为 $\gcd(X,a_p)$ 。

（tips: gcd 为最大公约数， $\gcd(0,x)=x$）

问对于所有 $1\leq i \leq m$ ，最终 $X=i$ 的方案数是多少。

两种方案不同，当且仅当存在一个 $i$ ，满足两种方案第 $i$ 轮选的 $p$ 不同。

答案对 $998244353$ 取模。

输入格式

第一行三个整数 $n,m,k$ 。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ 。

输出格式

输出一行 $m$ 个整数，第 $i$ 个表示最终 $X=i$ 的方案数。

样例1输入

6 6 2
1 1 4 5 1 4

样例1输出

31 0 0 4 1 0

数据范围

对于 $20\%$ 的数据，满足 $n,m,k\leq 5$ 。

对于 $40\%$ 的数据，满足 $n,m,k\leq 300$ 。

对于 $60\%$ 的数据，满足 $n,m,k\leq 5000$ 。

对于 $80\%$ 的数据，满足 $n,m,k\leq 10^5$ 。

对于全部数据，满足 $n,m\leq 10^6,1\leq k\leq 10^9$ 。