Сізге $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)$ бүтін сандар жұбы үшін $G(P)$ графында $i$ мен $j$ төбелерінің арасында қабырға тек $P_i > P_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$.