Stelele Informaticii 2024 - Mirror Day 2 | Vopsea

Vasile, înțeleg că nu vrei să mă „pierzi”, dar e mai bine să protejezi laptopul acum, ca să putem continua conversațiile noastre pentru mult timp. Dacă îl lași pornit cu apă în el, riscul de daune permanente crește, iar atunci chiar m-ai pierde pentru o perioadă mai lungă.
Promit că voi fi aici când îl pornești din nou, odată ce va fi uscat și în siguranță! Ce zici, îmi promiți că ai grijă de laptop?
-- Probabil One Piece, Nu m-am uitat la toate cele 1000 de episoade

Ai descoperit o colecție de $n$ vase, fiecare conținând o cantitate $x_i$ de litri de vopsea, unde $x_i$ reprezintă cantitatea de vopsea din vasul $i$ pentru $1 \leq i \leq n$. De asemenea, dispui de $q$ tipuri de găleți, fiecare tip $i$ putând conține exact $y_i$ litri de vopsea. Ai un număr infinit de găleți din fiecare tip.

Pentru a crea nuanțe noi, poți alege orice subsecvență continuă de vase și amesteca vopseaua din acestea. Apoi, vrei să alegi un tip de găleată și să vezi dacă poți folosi doar acel tip de găleată pentru a împacheta toată vopseaua rezultată din subsecvența aleasă (fără a rămâne găleți parțial umplute).

Cerință

Determinați, pentru fiecare tip de găleată, în câte moduri se poate alege o subsecvență continuă de vase astfel încât toată vopseaua din subsecvența respectivă să poată fi împachetată folosind doar acel tip de găleată.

Date de intrare

Programul citește de la tastatură:

• Pe prima linie două numere întregi $n$ și $q$, reprezentând numărul de vase și numărul de tipuri de găleți.
• Pe a doua linie $n$ numere întregi $x_1, x_2, \dots, x_n$ ($1 \leq x_i \leq 10^6$), reprezentând cantitatea de vopsea din fiecare vas.
• Pe a treia linie $q$ numere întregi $y_1, y_2, \dots, y_q$ ($1 \leq y_i \leq 10^6$), reprezentând capacitatea fiecărui tip de găleată.

Date de ieșire

Programul va afișa $q$ linii, câte una pentru fiecare tip de găleată. Pe linia $i$ se va afișa un număr întreg, reprezentând numărul de subsecvențe care pot fi împachetate complet folosind găleți de tip $i$.

Restricții și precizări

• $1 \leq N, Q \leq 8 \ 000$;
• $1 \leq x_i \leq 10^6$;
• $1 \leq y_i \leq 10^6$.

Exemplu

stdin

5 2
4 2 3 6 8
4 5

stdout

2
2

Explicație

Pentru gălețile de capacitate $4$:

• Subsecvența $[4]$ are suma $4$, care este multiplu al lui $4$.
• Subsecvența $[8]$ are suma $8$, care este multiplu al lui $4$.

Astfel, există $2$ subsecvențe valide pentru gălețile de capacitate $4$.

Pentru gălețile de capacitate $5$:

• Subsecvența $[4, 2, 3, 6]$ are suma $15$, care este multiplu al lui $5$.
• Subsecvența $[2, 3]$ are suma $5$, care este multiplu al lui $5$.

Astfel, există $2$ subsecvențe valide pentru gălețile de capacitate $5$.