[old] XOR mutacije 2

Perica se našao u veoma nezgodnoj poziciji. On je od svog profesora dobio niz pozitivnih cijelih brojeva A_1, A_2, \cdots, A_N dužine N. Kako svaka osoba ima svoje preferencije po pitanju operacija s bitovima, tako i Peričin profesor više voli and operaciju s bitovima u odnosu na operaciju xor, što je iznimno rijetka pojava.

Kako bi Perica udovoljio svom profesoru on će mu pokloniti jednu dobru nisku brojeva. Niska brojeva S_1, S_2, \cdots, S_M je dobra ako za svaki par brojeva (i, j) \ (1 \leq i \leq j \leq M) važi S_i \ and \ S_j > S_i \ xor \ S_j.

Pomozite Perici odgovoriti na Q upita, gdje je u svakom upitu dana podniska A_L, A_{L+1}, \cdots, A_R пpočetne niske, gdje je odgovor na upit dužina najduže dobre podsekvence te podniske. Preciznije, potrebno je naći najveće K tako da postoji niska indeksa L \leq i_1 < i_2 < \cdots < i_K \leq R takva da je niska A_{i_1}, A_{i_2}, \cdots, A_{i_K} dobra.

Opis ulaza

U prvoj liniji standardnog ulaza dana su dva cijela broja N i Q, broj elemenata niske i broj upita redom.

U drugoj liniji standardnog ulaza dano je N cijelih brojeva A_i, članova niske A.

U narednih Q linija standardnog ulaza dana su po dva cijela broja L i R, koji označavaju podnisku A_L, A_{L+1}, \cdots, A_R.

Opis izlaza

U Q linija standardnog izlaza potrebno je ispisati rješenje za svaki upit. U i-toj liniji se nalazi odgovor na i-ti upit.

Primjer 1

Ulaz

5 3
1 2 1 3 2
1 5
1 4
2 3

Izlaz

3
2
1

Objašnjenje

U prvom upitu najduža dobra niska je (2, \ 3, \ 2). Kako važi 2 \ and \ 2 > 2 \ xor \ 2, 2 \ and \ 3 > 2 \ xor \ 3 и 3 \ and \ 3 > 3 \ xor \ 3, ta niska je dobra. U drugom upitu najduža dobra niska je (2, \ 3), dok je u trećem upitu najduža dobra niska (2).

Ograničenja

• 1 \leq N, \ Q \leq 5 \cdot 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq L \leq R \leq N

Test primjeri su podijeljeni u 6 disjunktnih skupina:

• U testovima vrijednim 10 bodova: N, Q \leq 10
• U testovima vrijednim 15 bodova: A_i \leq 8
• U testovima vrijednim 20 bodova: svi članovi niske A su stupnjevi dvojke, tj. A_i = 2^{B_i} za neku nisku B
• U testovima vrijednim 20 bodova: N, Q \leq 5000
• U testovima vrijednim 15 bodova: N, Q \leq 10^5
• U testovima vrijednim 20 bodova: bez dodatnih ograničenja.

Napomena

Operator ekskluzivne disjunkcije u Pascalu označen je s xor, дdok u C++ ga zapisujemo s pomoću simbola ^. Ova operacija x\ \text{xor} \ y​ se za nenegativne cijele brojeve x,y​ definira na sljedeći način. Prvo se brojevi zapišu u binarnome zapisu. Ako jedan broj ima manje znamenki od drugoga, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih znamenki. Tako se dobivaju dvije niske binarnih znamenki, označimo ih s a_1, \ldots, a_k​ i b_1, \ldots b_k​. Zatim se za svaku poziciju i \in {1, \ldots, k }​ računa c_i​ s pomoću sljedećih pravila:

• Za a_{i} = 0, b_{i} = 0 važi c_{i} = 0
• Za a_{i} = 0, b_{i} = 1 važi c_{i} = 1
• Za a_{i} = 1, b_{i} = 0 važi c_{i} = 1
• Za a_{i} = 1, b_{i} = 1 važi c_{i} = 0

Niska binarnih znamenki c_1, \ldots, c_k (koja možda ima vodeće nule) je binarni zapis rezultata, odnosno broja x \ \text{xor} \ y.

Operator konjunkcije u Pascalu označen je s and, dok u C++ ga zapisujemo s pomoću simbola &. Ova operacija x\ \text{and} \ y​ se za nenegativne cijele brojeve x,y​ definira na sljedeći način. Prvo se brojevi zapišu u binarnome zapisu. Ako jedan broj ima manje znamenki od drugoga, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih znamenki. Tako se dobivaju dvije niske binarnih znamenki, označimo ih s a_1, \ldots, a_k​ i b_1, \ldots b_k​. Zatim se za svaku poziciju i \in \{1, \ldots, k \}​ računa c_i​ s pomoću sljedećih pravila:

• Za a_{i} = 0, b_{i} = 0 važi c_{i} = 0
• Za a_{i} = 0, b_{i} = 1 važi c_{i} = 0
• Za a_{i} = 1, b_{i} = 0 važi c_{i} = 0
• Za a_{i} = 1, b_{i} = 1 važi c_{i} = 1

Niska binarnih znamenki c_1, \ldots, c_k (koja možda ima vodeće nule) je binarni zapis rezultata, odnosno broja x \ \text{and} \ y.