XOR mutacije 2

Petrică s-a aflat într-o situație foarte incomodă. El a primit de la profesorul său un șir de numere întregi pozitive A_1, A_2, \cdots, A_N

de lungime N. Deoarece fiecare persoană are preferințele sale în privința operațiilor pe biți, profesorul lui Petrică preferă operația pe biți and în loc de operația xor, ceea ce este un fenomen foarte rar.

Pentru a-i face pe plac profesorului său, Petrică îi va oferi un șir de numere bun. Șirul de numere S_1, S_2, \cdots, S_M este considerat bun dacă pentru orice pereche de numere (i, j) \ (1 \leq i \leq j \leq M) este valabil S_i \ and \ S_j > S_i \ xor \ S_j.

Ajutați-l pe Petrică să răspundă la Q interogări, unde în fiecare interogare este dat un subșir A_L, A_{L+1}, \cdots, A_R al șirului inițial, iar răspunsul la interogare este lungimea celei mai lungi subsecvențe bune a acelui subșir. Mai precis, este necesar să găsiți cel mai mare K, astfel încât să existe un șir de indici L \leq i_1 < i_2 < \cdots < i_K \leq R, astfel încât șirul A_{i_1}, A_{i_2}, \cdots, A_{i_K} să fie bun.

Descrierea intrării

În prima linie a intrării standard, sunt date două numere întregi N și Q, numărul de elemente din șir și numărul de interogări, în această ordine.

În a doua linie a intrării standard, sunt date N numere întregi A_i, elementele șirului A.

În următoarele Q linii ale intrării standard, sunt date câte două numere întregi L și R, care reprezintă subșirul A_L, A_{L+1}, \cdots, A_R.

Descrierea ieșirii

În cele Q linii ale ieșirii standard, este necesar să se afișeze soluția pentru fiecare interogare. În cea de-a i linie se află răspunsul pentru cea de-a i interogare.

Exemplul 1

Intrare

5 3

1 2 1 3 2

1 5

1 4

2 3

Ieșire

3

2

1

Explicație

În prima interogare, cea mai lungă secvență bună este (2, \ 3, \ 2). Deoarece 2 \ and \ 2 > 2 \ xor \ 2, 2 \ and \ 3 > 2 \ xor \ 3 i 3 \ and \ 3 > 3 \ xor \ 3, această secvență este bună. În a doua interogare, cea mai lungă secvență bună este (2, \ 3), iar în a treia interogare, cea mai lungă secvență bună este (2).

Restricții

• 1 \leq N, \ Q \leq 5 \cdot 10^5

• 1 \leq A_i \leq 10^9

• 1 \leq L \leq R \leq N

Exemplele de test sunt împărțite în 6 grupuri disjuncte:

• În testele care valorează 10 puncte: N, Q \leq 10

• În testele care valorează 20 puncte: A_i \leq 8

• În testele care valorează 20 puncte: toate elementele șirului A sunt puteri ale lui doi, adică A_i = 2^{B_i} pentru un B

• În testele care valorează 20 puncte: N, Q \leq 5000

• În testele care valorează 15 puncte: N, Q \leq 10^5

• În testele care valorează 20 puncte: fără restricții suplimentare.

Notă

Operatorul de disjuncție exclusivă în Pascal este notat cu xor, în timp ce în C++ se scrie folosind simbolul^. Această operație x\ \text{xor} \ y​ pentru numere întregi nenegative x,y​ se definește astfel. Mai întâi, numerele se scriu în reprezentare binară. Dacă un număr are mai puține cifre decât celălalt, i se adaugă zerouri la început până când ambele au același număr de cifre binare. Astfel se obțin două șiruri de cifre binare, pe care le notăm cu a_1, \ldots, a_k​ și b_1, \ldots b_k​. Apoi, pentru fiecare poziție i \in {1, \ldots, k }​ se calculează c_i​ folosind următoarele reguli:

• Pentru a_{i} = 0, b_{i} = 0 este valabil c_{i} = 0

• Pentru a_{i} = 0, b_{i} = 1 este valabil c_{i} = 1

• Pentru a_{i} = 1, b_{i} = 0 este valabil c_{i} = 1

• Pentru a_{i} = 1, b_{i} = 1 este valabil c_{i} = 0

Șirul de cifre binare c_1, \ldots, c_k (care poate avea zerouri la început) reprezintă scrierea binară a rezultatului, adică numărul x \ \text{xor} \ y.

Operatorul de conjuncție în Pascal este notat cu and, în timp ce în C++ se scrie folosind simbolul &. Această operație x\ \text{and} \ y​ pentru numere întregi nenegative x,y​ se definește astfel. Mai întâi, numerele se scriu în reprezentare binară. Dacă un număr are mai puține cifre decât celălalt, i se adaugă zerouri la început până când ambele au același număr de cifre binare. Astfel se obțin două șiruri de cifre binare, pe care le notăm cu a_1, \ldots, a_k​ şi b_1, \ldots b_k​. Apoi, pentru fiecare poziție i \in \{1, \ldots, k \}​ se calculează c_i​ folosind următoarele reguli:

• Pentru a_{i} = 0, b_{i} = 0 este valabil c_{i} = 0

• Pentru a_{i} = 0, b_{i} = 1 este valabil c_{i} = 0

• Pentru a_{i} = 1, b_{i} = 0 este valabil c_{i} = 0

• Pentru a_{i} = 1, b_{i} = 1 este valabil c_{i} = 1

Șirul de cifre binare c_1, \ldots, c_k (care poate avea zerouri la început) reprezintă scrierea binară a rezultatului, adică numărul x \ \text{and} \ y.