Operatii

John este pasionat de șiruri de numere și de operații matematice pe intervale. El se confruntă cu următoarea problemă: se dă un șir $A$ format din $N$ numere naturale strict pozitive și $Q$ interogări, fiecare fiind de tipul $1$ sau tipul $2$.

Interogare de tip 1: Pentru o pereche $(ST, V_{\text{max}})$, unde $ST$ este indicele de start și $V_{\text{max}}$ este o valoare limită, se cere cel mai mare indice $DR$ ($ST \le DR \le N$) astfel încât produsul elementelor din secvența $A[ST \dots DR]$ să fie mai mic sau egal cu $V_{\text{max}}$:

Dacă $A[ST] > V_{\text{max}}$, răspunsul pentru interogare este $-1$.

Interogare de tip 2: Pentru o pereche $(ST, V_{\text{min}})$, unde $ST$ este indicele de start și $V_{\text{min}}$ este o valoare limită, se cere cel mai mare indice $DR$ ($ST \le DR \le N$) astfel încât rezultatul operației AND pe biți aplicate asupra tuturor elementelor secvenței $A[ST \dots DR]$ să fie mai mare sau egal cu $V_{\text{min}}$:

Dacă $A[ST] < V_{\text{min}}$, răspunsul pentru interogare este $-1$.

Date de intrare

Prima linie conține două numere naturale $N$ și $Q$, separate printr-un spațiu. A doua linie conține $N$ numere naturale separate prin spații, reprezentând elementele șirului $A$.

Fiecare dintre următoarele $Q$ linii conține câte trei numere naturale: tipul interogării $T$ ($T \in \{1, 2\}$), indicele de start $ST$ și valoarea limită $L$ (reprezentând $V_{\text{max}}$ pentru interogările de tip $1$, respectiv $V_{\text{min}}$ pentru interogările de tip $2$).

Date de ieșire

Fișierul de ieșire va conține $Q$ linii. Linia $i$ va conține răspunsul pentru a $i$-a interogare: un număr natural reprezentând indicele maxim $DR$, sau $-1$ dacă nu există niciun indice valid care să respecte condiția.

Restricții și precizări

• $1 \le N \le 100 \ 000$
• $1 \le Q \le 50 \ 000$
• $1 \le A[i] \le 10^9$ pentru orice $1 \le i \le N$
• $1 \le V_{\text{max}} \le 10^{18}$ pentru interogările de tip $1$
• $0 \le V_{\text{min}} \le 10^9$ pentru interogările de tip $2$

Exemplul 1

operatii.in

5 5
12 4 15 5 3
1 1 50
1 2 100
1 3 4
2 2 5
2 3 4

operatii.out

2
3
-1
-1
4

Explicații

Șirul este $A = [12, 4, 15, 5, 3]$.

Interogarea 1 (tip $1$, $ST=1$, $V_{\text{max}}=50$): $A[1] = 12 \le 50$, valid; $A[1] \cdot A[2] = 12 \cdot 4 = 48 \le 50$, valid; $A[1] \cdot A[2] \cdot A[3] = 48 \cdot 15 = 720 > 50$, invalid. Indicele maxim $DR$ este 2.

Interogarea 2 (tip $1$, $ST=2$, $V_{\text{max}}=100$): $A[2] = 4 \le 100$, valid; $A[2] \cdot A[3] = 4 \cdot 15 = 60 \le 100$, valid; $A[2] \cdot A[3] \cdot A[4] = 60 \cdot 5 = 300 > 100$, invalid. Indicele maxim $DR$ este 3.

Interogarea 3 (tip $1$, $ST=3$, $V_{\text{max}}=4$): $A[3] = 15 > 4$. Se afișează -1.

Interogarea 4 (tip $2$, $ST=2$, $V_{\text{min}}=5$): $A[2] = 4 < 5$. Se afișează -1.

Interogarea 5 (tip $2$, $ST=3$, $V_{\text{min}}=4$): $A[3] = 15 \ge 4$, valid; $A[3] \mathbin{\&} A[4] = 15 \mathbin{\&} 5 = 5 \ge 4$, valid; $A[3] \mathbin{\&} A[4] \mathbin{\&} A[5] = 5 \mathbin{\&} 3 = 1 < 4$, invalid. Indicele maxim $DR$ este 4.