俾你整數 $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$，設 $\mathcal{S}_d$ 為所有滿足以下全部條件嘅 $(1, 2, \dots, N)$ 嘅排列 $P$ 所組成嘅集合：

• $G(P)$ 係一棵樹。
• $G(P)$ 嘅直徑係 $d$。

對於每個詢問 $q = 1, 2, \dots, Q$，計算

$$\sum_{P \in \mathcal{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$。