cealaltacusumacifrelor

- Ai văzut problema aia cu suma cifrelor?
- Nu, dar am văzut problema cealaltă cu suma cifrelor.

Cerință

Prof. $\lambda$ are în notițele sale un număr $N$ și o listă de $N$ numere naturale. Costel, student, vine la el cu $Q$ numere diferite $x_1, x_2, \dots x_q$ și îl roagă ca pentru fiecare număr $x_i$, să aplice un număr cât mai mic de farmece asupra lui $x_i$ pentru ca acesta să ajungă să aibă suma cifrelor divizibilă cu $9$. Un farmec constă în una din următoarele operații:

• Prof. $\lambda$ alege un număr $v_j$ din lista sa și aplică operația $x_i = x_i + v_j$;
• Prof. $\lambda$ alege un număr $v_j$ din lista sa și aplică operația $x_i = x_i \cdot v_j$.

Care este numărul minim de farmece pe care Prof. $\lambda$ trebuie să-l realizeze pentru fiecare număr din cele date de Costel, astfel încât numărul rezultat să aibă suma cifrelor divizibilă cu $9$? Dacă acest lucru este imposibil, răspunsul va fi $-1$.

Date de intrare

Pe prima linie se va afla numărul $N$. Pe a doua linie se for afla $N$ întregi $v_1, v_2, \dots, v_n$ cu semnificația din enunț. Următoarea linie va conține $Q$, reprezentând numărul de întrebări ale lui Costel. Ultima linie conține $Q$ întregi $x_1, x_2, \dots, x_q$ cu semnificația din enunț.

Date de ieșire

Pe prima linie se va afișa pentru fiecare număr $x_i$ din cele date de Costel, numărul minim de farmece necesar pentru ca acesta să aibă suma cifrelor divizibilă cu $9$, sau $-1$ dacă acest lucru este imposibil.

Restricții

• $1 \leq N, Q \leq 2 \cdot 10^5$;
• $1 \leq v_i, \leq 10^9, 1 \leq i \leq N$;
• $1 \leq x_i, \leq 10^9, 1 \leq i \leq Q$;
• Pentru teste în valoare de $15$ puncte, există $1 \leq i \leq N$ a.î. $v_i \mod 9 = 0$;
• Pentru alte teste în valoare de $10$ puncte, există $1 \leq i \leq N$ a.î. $v_i \mod 3 = 0$;
• Pentru alte teste în valoare de $35$ de puncte, $N, Q \leq 100$;
• Pentru alte teste în valoare de $30$ de puncte, $Q \leq 30, N \leq 10^5$;

Exemplu

stdin

3
10 20 5
3
8 14 67

stdout

1 2 1

Explicație

• $8 + 10 = 18$, iar $1 + 8 = 9$
• $14 + 20 + 20 = 54$, iar $5 + 4 = 9$
• $67 + 5 = 72$, iar $7 + 2 = 9$