Vopsea

Time limit: 1s Memory limit: 512MB Input: Output:

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 nn vase, fiecare conținând o cantitate xix_i de litri de vopsea, unde xix_i reprezintă cantitatea de vopsea din vasul ii pentru 1in1 \leq i \leq n. De asemenea, dispui de qq tipuri de găleți, fiecare tip ii putând conține exact yiy_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 nn și qq, reprezentând numărul de vase și numărul de tipuri de găleți.
  • Pe a doua linie nn numere întregi x1,x2,,xnx_1, x_2, \dots, x_n (1xi1061 \leq x_i \leq 10^6), reprezentând cantitatea de vopsea din fiecare vas.
  • Pe a treia linie qq numere întregi y1,y2,,yqy_1, y_2, \dots, y_q (1yi1061 \leq y_i \leq 10^6), reprezentând capacitatea fiecărui tip de găleată.

Date de ieșire

Programul va afișa qq linii, câte una pentru fiecare tip de găleată. Pe linia ii 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 ii.

Restricții și precizări

  • 1N,Q8 0001 \leq N, Q \leq 8 \ 000;
  • 1xi1061 \leq x_i \leq 10^6;
  • 1yi1061 \leq y_i \leq 10^6.
# Punctaj Restricții
1 10 q=1q = 1 și y1>i=1Nxiy_1 > \sum_{i=1}^N x_i
2 20 N60N \leq 60, Q100Q \leq 100
3 30 N500N \leq 500, Q1 000Q \leq 1 \ 000
4 40 Fără restricții suplimentare.

Exemplu

stdin

5 2
4 2 3 6 8
4 5

stdout

2
2

Explicație

Pentru gălețile de capacitate 44:

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

Astfel, există 22 subsecvențe valide pentru gălețile de capacitate 44.

Pentru gălețile de capacitate 55:

  • Subsecvența [4,2,3,6][4, 2, 3, 6] are suma 1515, care este multiplu al lui 55.
  • Subsecvența [2,3][2, 3] are suma 55, care este multiplu al lui 55.

Astfel, există 22 subsecvențe valide pentru gălețile de capacitate 55.

Log in or sign up to be able to send submissions!