McProgres

Cerință

Se dă $n$, un șir $a$ de $n$ numere naturale și $q$ întrebări de forma:

• $1 \ \text{x} \ \text{poz}$: Elementul $a_{poz}$ devine $x$.
• $2 \ \text{l} \ \text{r}$: Ar fi subsecvența $[l, r]$ o progresie aritmetică, dacă aceasta ar fi sortată crescător?

Un șir $b$ de $m$ elemente este o progresie aritmetică dacă există un număr $\bold{real \ strict \ pozitiv}$ $c$, astfel încât $b_i=b_{i-1}+c$, $1<i \leq m$.

Date de intrare

Pe prima linie se vor afla $n$ și $q$. Pe a doua linie se va afla șirul $a$, iar pe următoarele $q$ linii se vor afla întrebările.

Date de ieșire

Pe următoarele linii se vor afișa răspunsurile la întrebările de tipul $2$.

Restricții și precizări

• $1 \leq n \leq 200 \ 000$;
• $1 \leq q \leq 100 \ 000$;
• $1 \leq a_i, x \leq 10^9$;
• $1 \leq poz, l, r \leq n$, $l \leq r$;
• Notă! La o întrebare de tipul $2$ se sortează subsecvența, însă această modificare nu este permanentă (după întrebare se revine la ce era înainte).

Exemplul 1

stdin

9 10
3 6 9 12 15 7 5 3 1
2 1 5
2 6 9
2 3 5
2 2 4
2 1 6
1 18 6
2 1 6
2 7 9
1 10 1 
2 1 5

stdout

DA
DA
DA
DA
NU
DA
DA
NU

Explicație

La prima întrebare, subsecvența este deja crescătoare și este progresie aritmetică.
La a doua întrebare, dacă sortăm subsecvența, aceasta devine $3 \ 5 \ 7$, care este o progresie aritmetică.
La a cincea întrebare, dacă sortăm subsecvența, aceasta devine $3 \ 6 \ 7 \ 9 \ 12 \ 15$, care nu este o progresie aritmetică, dar dupa a șasea întrebare, unde $a_6$ devine $18$, subsecvența în ordine crescătoare este $3 \ 6 \ 9 \ 12 \ 15 \ 18$, care este o progresie aritmetică.