Fişierul intrare/ieşire:	monezi2.in, monezi2.out	Sursă	Concursul National Urmasii lui Moisil 2012, Clasa a 10-a
Autor	Tudose Vlad Andrei	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Monezi2

Aurel are N tipuri de monezi de valori v₁,v₂,...,v_N. De fiecare dată când vrea să plăteasca o anumită sumă de bani, Aurel respectă următoarea condiţie: pentru oricare două tipuri de monezi i şi j, cu 1 ≤ i < j ≤ n, el va folosi cel puţin la fel de multe monezi de tipul i ca şi monezi de tipul j.

Cerinţă

Scrieţi un program care să-l ajute pe Aurel să verifice dacă poate plăti anumite sume de bani, respectând condiţia de mai sus.

Date de intrare

Pe prima linie a fişierului de intrare monezi2.in se află numărul natural N reprezentând numărul de tipuri de monezi. Pe următoarea linie se află numerele v₁,v₂,...,v_N, separate prin câte un spaţiu. Pe a treia linie se află numărul Q de sume de bani pe care Aurel doreşte să le verifice dacă pot fi plătite respectând condiţia din enunţ. Pe următoarele Q linii se află numerele s₁,s₂,...,s_Q reprezentând cele Q sume de bani, câte unul pe fiecare linie.

Date de ieşire

Fişierul de ieşire monezi2.out va conţine Q linii. Pe linia i se va afişa cuvântul DA în cazul în care suma s_i poate fi plătită. În caz contrar se va afişa cuvântul NU.

Restricţii

• 1 ≤ n ≤ 50
• 1 ≤ Q ≤ 10 000
• 1 ≤ v_i ≤ 1000
• 1 ≤ s_i ≤ 100 000
• Aurel dispune de un număr nelimitat de monezi pentru fiecare tip

Exemplu

Explicaţie

Suma 14 poate fi plătită folosind 3 monezi de tipul 1 şi o monedă de tipul 2.
Suma 10 nu poate fi plătită cu tipurile de monezi date, respectând condiţia din enunţ.

Cum se trimit solutii?