SMRAD

After a few months of building houses in Germany and earning a lot of money, Josip returned to Croatia. On his first evening back, he decided to take his friend Josipa out to dinner. Since they both enjoy good food and drinks, Josip visited the ATM $M$ times that evening and withdrew $X_i$ kuna each time. The ATM holds $N$ kinds of banknotes with different values, and each kind is available in unlimited quantity.

Each time Josip came to withdraw money, a notice was posted on the ATM: "Dear customers, due to a malfunction, all banknotes of value $C_i$ will now smell bad. Thank you for your understanding!"

Once banknotes of some value become smelly, they stay smelly forever.

To avoid unpleasant situations with smelly banknotes, Josip wants to know whether the ATM can pay exactly $X_i$ kuna, either in one withdrawal or in several smaller payments that add up to $X_i$, while being sure he will not receive a smelly banknote. Josip always asks the ATM for an amount that can be paid.

The first line contains natural numbers $N$ and $M$ ($1 \le M \le N \le 5000$), as given in the statement.

The second line contains $N$ natural numbers $A_i$ ($1 \le A_i \le 10000$, $i=1 \dots N$) separated by spaces, where $A_1$ is the value of the first kind of banknote, $A_2$ the value of the second kind, and so on up to $A_N$.

Each of the next $M$ lines contains two natural numbers $X_i$ and $C_i$ ($1 \le X_i \le 10000$, $1 \le C_i \le 10000$) separated by a space, where $X_i$ is the amount Josip wants to withdraw on his $i$-th visit, and $C_i$ is the value of the banknote that became smelly on his $i$-th visit.

On each of the $M$ lines, print "DA" if Josip can withdraw exactly $X_i$ kuna on his $i$-th visit without receiving any smelly banknote, otherwise print "NE".

On the first visit, Josip cannot ask for 11 kuna in a single payment, because the ATM could give him a 5 kuna note and a smelly 6 kuna note. He can ask for three payments instead: one of 1 kuna and two of 5 kuna. None of these three payments can be made with the smelly note, and together they total the 11 kuna he wanted. On the second visit, Josip cannot withdraw 11 kuna without risking at least one smelly banknote.