chmax

Raul și Deniz se joacă Adevărat sau Fals. Ei fiind informaticieni, au schimbat setările jocului, iar acum întrebările sunt diferite. Jocul acum se desfășoară astfel:

1. Raul și Deniz primesc numerele $N, Q$ și un șir $a_1 \ a_2 \ \dots \ a_N$ de numere naturale.
2. Urmează $Q$ întrebări de forma: "Ți se dau numerele $l$, $r$ și $p$ ($1 \leq l \leq p \leq r \leq N$). Spune dacă $a_p$ este egal cu $max(a_l, a_{l+1} \dots a_r)$". Raul și Deniz trebuie să afle cât mai repede dacă trebuie să zică Adevărat sau Fals.

Cerință

Pentru a răspunde foarte repede la întrebări, te-au rugat pe tine să îi ajuți să scrii un program care răspunde cât mai repede la aceste întrebări.

Date de intrare

Pe prima linie se găsesc două numere naturale, $N$ și $Q$.

Pe a doua linie se află $N$ numere naturale, reprezentând șirul $a_1 \ a_2 \ \dots \ a_N$.

Pe următoarele $Q$ linii se află câte un triplet de numere, reprezentând $l$, $r$ și $p$, în această ordine.

Date de ieșire

Se afișează un șir de $Q$ caractere, al $i$-lea caracter fiind $1$ dacă răspunsul la a $i$-a interogare este adevărat, iar $0$ altfel.

Restricții și precizări

• $1 \leq N, Q \leq 10^6$
• $a_i \leq 10^9$
• Se recomandă să se afișeze tot șirul de caractere ($0$ sau $1$) o singură dată, la finalul interogărilor

Exemplul 1

stdin

8 12
1 5 5 2 4 9 3 2
1 2 2
1 2 1
2 3 2
2 3 2
2 4 3
2 4 4
2 4 2
1 6 6
7 8 8
4 5 4
3 6 3
3 6 6

stdout

101110110001

Explicație

$N = 8$, $Q = 12$

$a = [1, 5, 5, 2, 4, 9, 3, 2]$

Răspunsul la prima întrebare este adevărat deoarece $l = 1$, $r = 2$, $p = 2$, $a_p = 2$, iar $max(a_1, a_2) = max(1, 5) = 5$. Deci $a_2 = max(a_1, a_2)$. Așadar, trebuie afișat caracterul $1$.

Răspunsul la a doua întrebare este fals deoarece $l = 1$, $r = 2$, $p = 2$, $a_p = 1$, dar $max(a_1, a_2) = 5 \neq a_1$ Așadar, trebuie afișat caracterul $0$.

Răspunsul la a cincea întrebare este adevărat deoarece $l = 2$, $r = 4$, $p = 3$, iar $a_p = a_3 = max(a_2, a_3, a_4) = max(5, 5, 2) = 5$. Așadar, caracterul afișat pe a cincea poziție este $1$.