Вам дано цілі числа $N, K$ та цілочисельну послідовність $D = (D_1, D_2, \dots, D_Q)$ довжини $Q$.

Для перестановки $P = (P_1, P_2, \dots, P_N)$ чисел $(1, 2, \dots, N)$ визначимо неорієнтований граф $G(P)$ з вершинами $1, 2, \dots, N$ таким чином:

Для кожної пари цілих чисел $(i, j)$ з умовою $1 \le i < j \le N$ ребро між вершинами $i$ та $j$ у $G(P)$ існує тоді й лише тоді, коли $P_i > P_j$.

Для кожного $d = 1, 2, \dots, N - 1$ позначимо через $\mathcal{S}_d$ множину всіх перестановок $P$ чисел $(1, 2, \dots, N)$, які задовольняють усі наведені нижче умови:

• $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

Примітка

У першому прикладі перестановками $P$ чисел $(1, 2, 3, 4)$, для яких $G(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$.