Marius Nicoli (mariusn) Cerința
A venit ora mesei pentru Por Costel (masa dintre prânz și cină). Scormonind printr-o grădină, el descoperă un număr de N coceni de porumb și M mere. Masa lui Por Costel va consta în exact un cocean și un măr. Însă, mai nou, fanii săi l-au atenționat că trebuie să aibă grijă ce mănâncă. Fiecare cocean și fiecare măr are o valoare nutritivă. Valoarea nutritivă a mesei va fi valoarea nutritivă a coceanului ales + valoarea nutritiva a mărului ales. Dându-se valorile nutritive ale cocenilor și ale merelor, Por Costel vă întreabă dacă există o masă pe care o poate lua cu valoare nutritivă X. Pentru că Por Costel vrea sa mănânce de mai multe ori între prânz și cină, el va vă pune T întrebări de forma aceasta.
(Întrebările sunt independente între ele, a nu se considera că după o întrebare se elimină perechea cocean-mar aleasă).
Date de intrare
Pe prima linie a fișierului gustare.in se găsește un număr natural N: numărul de coceni. Pe a doua linie se găsește o secvență de N numere naturale separate prin câte un spațiu (valorile nutritive ale cocenilor). Pe a treia linie se găsește un număr natural M: numărul de mere. Pe a patra linie se găsește o secvență de M numere naturale separate prin câte un spațiu (valorile nutritive ale merelor). Pe a cincea linie se găsește un număr natural T, numărul de întrebări ale lui Por Costel. Pe a sasea linie se gasește o secvență de T numere naturale separate prin câte un spațiu, al i-lea număr fiind valoarea dorită pentru cea de a i-a masă.
Date de ieșire
În fișierul gustare.out se vor scrie T linii corespunzătoare celor T întrebări. A i-a linie va conține mesajul DA dacă se poate forma valoarea nutritivă pentru a i-a masă și NU în caz contrar.
Restricții și precizări
N, M ≤ 500.000T ≤ 1000 ≤valoare nutritiva a unui aliment≤ 1.000.000.0000 ≤valoareaXa unei intrebari≤ 2.000.000.000- Pentru
20de puncte,N, M ≤ 1000 - Pentru alte
50de puncte,T ≤ 20
Exemplu:
gustare.in
4 2 2 3 5 3 2 4 6 5 6 20 10 11 7
gustare.out
DA NU NU DA DA