supremacusumacifrelor

"I'd just like to interject for a moment. What you're referring to as Linux, is in fact, Windows/WSL, or as I've recently taken to calling it, Windows plus WSL. Linux is not an operating system unto itself, but rather another free component of a fully functioning Windows/WSL system made useful by the WinAPI corelibs, shell utilities and vital system components comprising a full OS as implemented by Microsoft."

Cerință

Windows Subsystem for Linux (WSL) s-a săturat să fie subiectul glumelor și s-a hotărât să arate ce poate, rezolvând probleme grele de informatică. El are acum la dispoziție $N$ numere naturale $v_1, v_2, \dots, v_N$.

WSL pornește de la un număr natural $x$, asupra căruia dorește să aplice niște farmece. Aplicarea unui farmec constă în selectarea unui indice $j$ ($1 \leq j \leq N$) și înlocuirea lui $x$ cu valoarea $x + v_j$. Același indice poate fi ales de mai multe ori. O secvență de exact $K$ farmece este considerată validă dacă, după aplicarea acestora, suma cifrelor reprezentării în baza $B$ a valorii finale este divizibilă cu $B-1$. Determinați numărul secvențelor valide, modulo $998\,244\,353$.

WSL a rezolvat această problemă cu ușurință. Din această cauză, prof. $\$$ vine la el cu $Q$ numere $x_1, x_2, \dots, x_Q$ și dorește răspunsul pentru fiecare dintre acestea. Ajutați-l pe WSL să răspundă acestor cereri.

Date de intrare

Pe prima linie se găsesc trei numere întregi, $N$, $B$, și $K$. Pe următoarea linie se găsesc $N$ numere întregi $v_1, v_2, \dots, v_N$. Pe a treia linie se găsește un număr întreg, $Q$, reprezentând numărul de interogări ale lui prof. $\$$. Pe ultima linie se găsesc cele $Q$ numere naturale $x_1, x_2, \dots, x_Q$, unde $x_i$ reprezinta valoarea inițiala pentru fiecare interogare.

Date de ieșire

Se vor afișa $Q$ linii. Pe a $i$-a linie se va afișa un număr reprezentând numărul de secvențe valide (modulo $998 \ 244 \ 353$) pentru a $i$-a interogare.

Restricții și precizări

• $1 \leq N, Q \leq 200 \ 000$;
• $2 \leq B \leq 100 \ 000$;
• $1 \leq K \leq 10^9$;
• $0 \leq v_i, x_i \leq 10^9$;
• Pentru teste în valoare de 17 puncte, $K = 1$;
• Pentru alte teste în valoare de 21 puncte, $K = 2$;
• Pentru alte teste în valoare de 21 de puncte, $K, N, B \leq 100$;
• Pentru alte teste în valoare de 19 de puncte, $B \leq 1000$;
• Pentru restul de 22 de puncte, nu există restricții suplimentare;
• Două secvențe sunt considerate diferite dacă indicii aleși diferă pe cel puțin o poziție, chiar dacă valorile corespunzătoare sunt egale.

Exemplul 1

stdin

3 5 2
1 2 3
2
0 2

stdout

3
2

Explicație

Avem $N = 3$ farmece cu valorile $(1, 2, 3)$, baza $B = 5$, deci suma cifrelor trebuie să fie divizibilă cu $B-1 = 4$. Se aplică secvențe de exact $K = 2$ farmece.
Există două interogări:

1. Pentru $x = 0$, valoarea finală este suma celor $2$ farmece alese. Vrem ca suma lor să dea un rest $0$ modulo $4$. Secvențele de $2$ farmece valide sunt: $(1, 3)$, $(3, 1)$ și $(2, 2)$ deoarece $1+3 = 3+1 = 2+2 = 4$, iar $4$ modulo $4 = 0$. Răspuns: $3$.
2. Pentru $x = 2$, valoarea finală este $2 +$ suma celor $2$ farmece. Vrem ca $(2 + suma) \equiv 0 \pmod 4$, deci suma farmecelor trebuie să dea rest $2$ la împărțirea cu $4$. Secvențele valide sunt $(1, 1)$ și $(3, 3)$. Răspuns: $2$.

Exemplul 2

stdin

2 4 2
1 2
1
1

stdout

1

Explicație

Avem farmecele $(1, 2)$, $B=4$, $K=2$. Vrem divizibilitate cu $3$.
Pentru singurul query $x = 1$, căutăm o sumă a 2 farmece care adunată cu $1$ se împarte exact la $3$. Singura secvență formată din 2 farmece este $(1, 1)$ cu suma $2$, obținând valoarea finală $x = 1 + 2 = 3$. Răspunsul este $1$.