You are given integers $N, K$, and an integer sequence $D = (D_1, D_2, \dots, D_Q)$ of length $Q$.

For a permutation $P = (P_1, P_2, \dots, P_N)$ of $(1, 2, \dots, N)$, define an undirected graph $G(P)$ with vertices $1, 2, \dots, N$ as follows:

For each pair of integers $(i, j)$ with $1 \le i < j \le N$, there is an edge between vertices $i$ and $j$ in $G(P)$ if and only if $P_i > P_j$.

For each $d = 1, 2, \dots, N - 1$, let $\mathcal{S}_d$ be the set of all permutations $P$ of $(1, 2, \dots, N)$ that satisfy all of the following conditions:

• $G(P)$ is a tree.
• The diameter of $G(P)$ is $d$.

For each query $q = 1, 2, \dots, Q$, compute

$$\sum_{P \in \mathcal{S}_{D_q}} (\text{LIS}(P))^K \bmod 998244353,$$

where $\text{LIS}(P)$ denotes the length of the longest increasing subsequence of $P$.

Input

The input is given from Standard Input in the following format:

N K
Q
D_1
D_2
:
D_Q

• All input values are integers.
• $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$

Output

Print $Q$ lines in order.

The $q$-th line should contain the answer for $q$.

Examples

Sample Input 1

4 0
3
1
2
3

Sample Output 1

0
2
2

Sample Input 2

2 100
1
1

Sample Output 2

1

Sample Input 3

314159 26535
5
271
828
1828
45904
52353

Sample Output 3

765557189
351184939
258247317
305813889
68486796

Note

In the first example, the permutations $P$ of $(1, 2, 3, 4)$ such that $G(P)$ is a tree are exactly the following $4$ permutations:

• $P = (2, 3, 4, 1)$: the diameter of $G(P)$ is $2$, and $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: the diameter of $G(P)$ is $2$, and $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: the diameter of $G(P)$ is $3$, and $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: the diameter of $G(P)$ is $3$, and $\text{LIS}(P) = 2$.

Therefore:

• For $q = 1$, the answer is $0$.
• For $q = 2$, the answer is $3^0 + 3^0 = 2$.
• For $q = 3$, the answer is $2^0 + 2^0 = 2$.