给你整数 $N, K$ 以及一个长度为 $Q$ 的整数序列 $D = (D_1, D_2, \dots, D_Q)$。

对于一个 $(1, 2, \dots, N)$ 的排列 $P = (P_1, P_2, \dots, P_N)$，我们定义一个包含顶点 $1, 2, \dots, N$ 的无向图 $G(P)$ 如下：

对于每对满足 $1 \le i < j \le N$ 的整数 $(i, j)$，当且仅当 $P_i > P_j$ 时，在 $G(P)$ 中顶点 $i$ 和 $j$ 之间存在一条边。

对于每个 $d = 1, 2, \dots, N - 1$，令 $S_d$ 为满足以下所有条件的 $(1, 2, \dots, N)$ 的排列 $P$ 的集合：

• $G(P)$ 是一棵树。
• $G(P)$ 的直径为 $d$。

对于每个查询 $q = 1, 2, \dots, Q$，计算：

$$\sum_{P \in S_{D_q}} (\text{LIS}(P))^K \bmod 998244353$$

其中 $\text{LIS}(P)$ 表示 $P$ 的最长上升子序列的长度。

输入格式

输入从标准输入中以以下格式给出：

N K
Q
D_1
D_2
:
D_Q

数据范围

• 所有输入值均为整数。
• $2 \le N \le 10^6$
• $0 \le K \le 10^{18}$
• $1 \le Q \le 2 \times 10^5$
• $1 \le D_1 < D_2 < \dots < D_Q < N$

输出格式

依次输出 $Q$ 行。

第 $q$ 行应包含第 $q$ 个查询的答案。

样例

输入样例 1

4 0
3
1
2
3

输出样例 1

0
2
2

输入样例 2

2 100
1
1

输出样例 2

1

输入样例 3

314159 26535
5
271
828
1828
45904
52353

输出样例 3

765557189
351184939
258247317
305813889
68486796

说明

在第一个样例中，使得 $G(P)$ 是一棵树的 $(1, 2, 3, 4)$ 的排列 $P$ 恰好有以下 4 个：

• $P = (2, 3, 4, 1)$：$G(P)$ 的直径为 2，且 $\text{LIS}(P) = 3$。
• $P = (4, 1, 2, 3)$：$G(P)$ 的直径为 2，且 $\text{LIS}(P) = 3$。
• $P = (2, 4, 1, 3)$：$G(P)$ 的直径为 3，且 $\text{LIS}(P) = 2$。
• $P = (3, 1, 4, 2)$：$G(P)$ 的直径为 3，且 $\text{LIS}(P) = 2$。

因此：

• 对于 $q = 1$，答案为 0。
• 对于 $q = 2$，答案为 $3^0 + 3^0 = 2$。
• 对于 $q = 3$，答案为 $2^0 + 2^0 = 2$。