D - Antepenultimul Cox

Cerință

Se dă un șir de numere $A$ de lungime $N$ și $Q$ întrebari de tipul $St\ Dr\ X$.

Pentru fiecare întrebare să se răspundă:
Există o submulțime $\{i_1, i_2, ..., i_k\}$ a mulțimii $\{St, St+1, ..., Dr-1, Dr\}$ cu $i_1 < i_2 < ... < i_k$ și $A_{i_1} + A_{i_2} + ... + A_{i_k} = X$?

Date de intrare

Pe prima linie sunt $N$ și $Q$. Pe a doua linie este șirul $A$. Pe următoarele $Q$ linii se află câte $3$ numere: $St\ Dr\ X$.

Date de ieșire

$Q$ linii cu răspunsurile. Răspunsul este fie DA, fie NU.

Restrictii

• $1 \le N, X, A_i \le 10^3$;
• $1 \le St \le Dr \le N$;
• $1 \le Q \le 10^5$.

Exemplu

stdin

5 3
1 2 3 4 5
2 3 5
2 3 4
2 4 6

stdout

DA
NU
DA