يُعطى العددان الصحيحان $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$.