3955: day4T1

#### 题目描述

有 $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(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$ 的方案数。

#### 样例输入

```
6 6 2
1 1 4 5 1 4
```

#### 样例输出

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