Ti vengono dati gli interi $N, K$ e una sequenza di interi $D = (D_1, D_2, \dots, D_Q)$ di lunghezza $Q$.

Per una permutazione $P = (P_1, P_2, \dots, P_N)$ di $(1, 2, \dots, N)$, definiamo un grafo non orientato $G(P)$ con vertici $1, 2, \dots, N$ come segue:

Per ogni coppia di interi $(i, j)$ con $1 \le i < j \le N$, c'è un arco tra i vertici $i$ e $j$ in $G(P)$ se e solo se $P_i > P_j$.

Per ogni $d = 1, 2, \dots, N - 1$, sia $\mathcal{S}_d$ l'insieme di tutte le permutazioni $P$ di $(1, 2, \dots, N)$ che soddisfano tutte le seguenti condizioni:

• $G(P)$ è un albero.
• Il diametro di $G(P)$ è $d$.

Per ogni query $q = 1, 2, \dots, Q$, calcola

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

dove $\text{LIS}(P)$ indica la lunghezza della più lunga sottosequenza crescente di $P$.

Input

L'input è fornito dallo Standard Input nel seguente formato:

N K
Q
D_1
D_2
:
D_Q

• Tutti i valori di input sono interi.
• $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

Stampa $Q$ righe in ordine.

La $q$-esima riga deve contenere la risposta per $q$.

Esempi

Input di esempio 1

4 0
3
1
2
3

Output di esempio 1

0
2
2

Input di esempio 2

2 100
1
1

Output di esempio 2

1

Input di esempio 3

314159 26535
5
271
828
1828
45904
52353

Output di esempio 3

765557189
351184939
258247317
305813889
68486796

Nota

Nel primo esempio, le permutazioni $P$ di $(1, 2, 3, 4)$ tali che $G(P)$ sia un albero sono esattamente le seguenti $4$ permutazioni:

• $P = (2, 3, 4, 1)$: il diametro di $G(P)$ è $2$, e $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: il diametro di $G(P)$ è $2$, e $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: il diametro di $G(P)$ è $3$, e $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: il diametro di $G(P)$ è $3$, e $\text{LIS}(P) = 2$.

Pertanto:

• Per $q = 1$, la risposta è $0$.
• Per $q = 2$, la risposta è $3^0 + 3^0 = 2$.
• Per $q = 3$, la risposta è $2^0 + 2^0 = 2$.