SMRAD

독일에서 몇 달 동안 집을 짓고 돈을 많이 번 요시프가 크로아티아로 돌아왔다. 돌아온 첫날 저녁, 그는 친구 요시파를 저녁 식사에 초대하기로 했다. 둘 다 음식과 술을 좋아해서, 요시프는 그날 저녁 ATM에 $M$번 가서 매번 $X_i$ 쿠나씩 인출했다. 이 ATM에는 액면가가 서로 다른 지폐가 $N$종 있으며, 각 종류는 무제한으로 있다.

요시프가 돈을 인출하러 올 때마다 ATM에 안내문이 붙어 있었다. “고객 여러분, 기기 고장으로 인해 액면가 $C_i$인 지폐는 이제 냄새가 납니다. 양해해 주셔서 감사합니다!”

한번 냄새나는 지폐가 된 액면가는 그 뒤로 계속 냄새나는 지폐로 남는다.

식당에서 냄새나는 지폐와 마주치는 불편을 피하려고, 요시프는 ATM이 정확히 $X_i$ 쿠나를 한 번에 지급하거나, 합이 $X_i$가 되도록 여러 번 나누어 지급할 수 있는지 알고 싶어 한다. 단, 냄새나는 지폐를 받지 않는다고 확신할 수 있어야 한다. 요시프는 항상 지급 가능한 금액만 ATM에 요청한다.

첫째 줄에는 본문에 나온 자연수 $N$과 $M$ ($1 \le M \le N \le 5000$)이 주어진다.

둘째 줄에는 공백으로 구분된 자연수 $N$개 $A_i$ ($1 \le A_i \le 10000$, $i=1 \dots N$)가 주어진다. $A_1$은 첫 번째 종류 지폐의 액면가이고, $A_2$는 두 번째 종류의 액면가이며, 이런 식으로 $A_N$까지 이어진다.

다음 $M$개의 줄에는 각각 공백으로 구분된 자연수 $X_i$와 $C_i$ ($1 \le X_i \le 10000$, $1 \le C_i \le 10000$)가 주어진다. $X_i$는 $i$번째 방문에서 인출하려는 금액이고, $C_i$는 $i$번째 방문에서 냄새나게 된 지폐의 액면가이다.

$M$개의 줄마다, $i$번째 방문에서 냄새나는 지폐를 받지 않고 $X_i$ 쿠나를 인출할 수 있으면 “DA”, 그렇지 않으면 “NE”를 출력한다.

처음 방문에서는 ATM이 5쿠나 지폐와 냄새나는 6쿠나 지폐를 줄 수도 있으므로, 11쿠나를 한 번에 요청할 수 없다. 대신 1쿠나 한 번, 5쿠나 두 번, 이렇게 세 번에 나누어 요청할 수 있다. 세 번의 지급 중 어느 것도 냄새나는 지폐로 이루어지지 않으며, 합은 원하던 11쿠나이다. 두 번째 방문에서는 냄새나는 지폐를 적어도 한 장 받을 위험 없이 11쿠나를 인출할 방법이 없다.