Agar

Cerință

Intr-un agar se afla $n$ microbi. Fiecare microb poate fi caracterizat prin indexul sau $i$ $(0 \leq i \lt n)$ si puterea sa $p_i$.
Un microb $i$ poate manca microbul $j$ daca si numai daca:

• Cei doi microbi sunt diferiti: $i \ne j$
• Microbul $i$ este cel putin la fel de puternic ca microbul $j$: $p_i \geq p_j$
• Microbul $i$ nu are o putere mai mare de dublul puterii microbului $j$ (nici in lumea microbilor nu este frumos ca cei puternici sa-i atace pe cei slabi): $p_i \leq 2p_j$

De exemplu, un microb cu puterea 9 poate manca un microb cu puterea intre 5 si 9 si poate fi mancat de un microb cu puterea intre 9 si 18.
O multime de microbi se numeste anihilatoare daca este posibil ca microbii sa se manance intre ei astfel incat sa ramana un singur microb.

ATENTIE: O secventa este anihilatoare daca exista CEL PUTIN un scenariu in care microbii se mananca intre ei pana ramane unul singur. De exemplu, multimea de microbi cu puterile 3, 7 si 4 este anihilatoare, pe cand multimea de microbi cu puterile 3 si 7 nu este.

Oamenii de stiinta vor sa efectueze $m$ diferite experimente asupra microbilor si considera diferite scenarii, fiecare scenariu fiind caracterizat de doi indici $a$ si $b$ (0 \leq a \leq b \lt n). Pentru un scenariu particular ($a$, $b$), oamenii de stiinta izoleaza toti microbii cu indice $i$ cuprins intre $a$ si $b$ (inclusiv), urmand sa testeze daca multimea izolata de microbi este anihilatoare.

ATENTIE: Cele $m$ scenarii sunt pur teoretice si nu se influenteaza unul pe altul. Astfel, puteti considera ca pentru fiecare scenariu toti virusii sunt inca in viata.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $n$, care reprezinta numarul de microbi respectiv numarul de scenarii pe care le considera oamenii de stiinta. Urmatoarea linie contine $n$ numere $p_0, p_1$, ... , $p_n$$_-$$_1$.

Date de ieșire

Pentru fiecare din cele $m$ experimente, sa se afiseze cate o linie care sa contina DA daca este anihilatoare si NU in caz contrar.

Restricții și precizări

• $1 \leq n, m \leq 10^5$;
• $1 \leq p_i \leq 10^5$

Subtask-uri

Exemplul 1

stdin

3 3
3 7 4
0 1
0 2
1 2

stdout

NU
DA
DA

Exemplul 2

stdin

5 5
5 2 4 11 10
0 0
0 1
0 2
0 3
0 4

stdout

DA
NU
DA
NU
DA