Dane są liczby całkowite $N, K$ oraz ciąg liczb całkowitych $D = (D_1, D_2, \dots, D_Q)$ o długości $Q$.

Dla permutacji $P = (P_1, P_2, \dots, P_N)$ zbioru $(1, 2, \dots, N)$ definiujemy graf nieskierowany $G(P)$ o wierzchołkach $1, 2, \dots, N$ w następujący sposób:

Dla każdej pary liczb całkowitych $(i, j)$ spełniającej $1 \le i < j \le N$, krawędź między wierzchołkami $i$ oraz $j$ w $G(P)$ istnieje wtedy i tylko wtedy, gdy $P_i > P_j$.

Dla każdego $d = 1, 2, \dots, N - 1$ niech $\mathcal{S}_d$ oznacza zbiór wszystkich permutacji $P$ zbioru $(1, 2, \dots, N)$, które spełniają wszystkie poniższe warunki:

• $G(P)$ jest drzewem.
• Średnica grafu $G(P)$ wynosi $d$.

Dla każdego zapytania $q = 1, 2, \dots, Q$ oblicz

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

gdzie $\text{LIS}(P)$ oznacza długość najdłuższego rosnącego podciągu permutacji $P$.

Wejście

Wejście jest podawane ze standardowego wejścia w następującym formacie:

N K
Q
D_1
D_2
:
D_Q

• Wszystkie wartości wejściowe są liczbami całkowitymi.
• $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$

Wyjście

Wypisz kolejno $Q$ wierszy.

W $q$-tym wierszu powinna znaleźć się odpowiedź dla $q$.

Przykłady

Przykładowe wejście 1

4 0
3
1
2
3

Przykładowe wyjście 1

0
2
2

Przykładowe wejście 2

2 100
1
1

Przykładowe wyjście 2

1

Przykładowe wejście 3

314159 26535
5
271
828
1828
45904
52353

Przykładowe wyjście 3

765557189
351184939
258247317
305813889
68486796

Uwaga

W pierwszym przykładzie permutacjami $P$ zbioru $(1, 2, 3, 4)$, dla których $G(P)$ jest drzewem, są dokładnie następujące $4$ permutacje:

• $P = (2, 3, 4, 1)$: średnica $G(P)$ wynosi $2$, a $\text{LIS}(P) = 3$.
• $P = (4, 1, 2, 3)$: średnica $G(P)$ wynosi $2$, a $\text{LIS}(P) = 3$.
• $P = (2, 4, 1, 3)$: średnica $G(P)$ wynosi $3$, a $\text{LIS}(P) = 2$.
• $P = (3, 1, 4, 2)$: średnica $G(P)$ wynosi $3$, a $\text{LIS}(P) = 2$.

Zatem:

• Dla $q = 1$ odpowiedź wynosi $0$.
• Dla $q = 2$ odpowiedź wynosi $3^0 + 3^0 = 2$.
• Dla $q = 3$ odpowiedź wynosi $2^0 + 2^0 = 2$.