#0007CA

[ol2] XOR mutacije 2

Перица ше нашол у барз нєзґодней позициї. Вон од свойого професора достал шор позитивних цалих числох A_1, A_2, \cdots, A_N длужини N. Понеже кажда особа ма свойо преференци по питаню битовских операцийох, так и Перицов професор баржей люби битовску операцию and у одношеню на операцию xor, цо досц нєкаждоньове зявенє.

Же би Перица задоволєл свойого професора вон му подарує єден добри шлїд числох. Шлїд числох S_1, S_2, \cdots, S_M добри кед же за кажду пару числох (i, j) \ (1 \leq i \leq j \leq M) важи S_i \ and \ S_j > S_i \ xor \ S_j.

Помогнїце Перицови же би одвитовал на Q питаня, дзе у каждим питаню дати подшлїд A_L, A_{L+1}, \cdots, A_R початного шлїду, дзе одвит на питанє длужина найдлукшей добрей подсеквенци того подшлїду. Прецизнєйше, потребне найсц найвекши K так же би исновал шлїд индексох L \leq i_1 < i_2 < \cdots < i_K \leq R таки же шлїд A_{i_1}, A_{i_2}, \cdots, A_{i_K} добри.

Опис уходу

У першей линиї стандардного уходу дати два цали числа N и Q, число елементох того шлїду и число питаньох по шоре.

У другей линиї стандардного уходу дати N цали числа A_i, члени шлїду A.

У шлїдуюцих Q линийох стандардного уходу дати по два цали числа L и R, хтори означую подшлїд A_L, A_{L+1}, \cdots, A_R.

Опис виходу

У Q линийох стандардного виходу потребне виписац ришенє за кажде питанє. У i-тей линиї ше находзи одвит на i-те питанє.

Приклад 1

Уход

Виход

3
2
1

Толкованє

У першим питаню найдлукши добри шлїд то (2, \ 3, \ 2). Понеже важи 2 \ and \ 2 > 2 \ xor \ 2, 2 \ and \ 3 > 2 \ xor \ 3 и 3 \ and \ 3 > 3 \ xor \ 3, тот шлїд добри. У другим питаню найдлукши добри шлїд то (2, \ 3), док у трецим питаню найдлугши добри шлїд (2).

Огранїченя

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

Тест приклади подзелєни до 6 дисюнктних ґрупох:

на тестох хтори вредза 10 поени: N, Q \leq 10
на тестох хтори вредза 15 поени: A_i \leq 8
на тестох хтори вредза 20 поени: шицки члени шлїду A то ступнї двойки, тє. A_i = 2^{B_i} за даяки шлїд B
на тестох хтори вредза 20 поени: N, Q \leq 5000
на тестох хтори вредза 15 поени: N, Q \leq 10^5
на тестох хтори вредза 20 поени: без додатних огранїченьох.

Надпомнуце

Оператор ексклузивней дисюнкциї у Pascal-u означени зоз xor, док го у C++ записуєме з помоцу симболу ^. Тота операция x\ \text{xor} \ y ше за нєнеґативни цали числа x,y дефинує на шлїдуюци способ. Перше ше числа запишу у бинарном запису. Кед же єдно число ма менєй цифри од другого, дописую му ше водзаци нули покля ше нє виєднача числа бинарних цифрох. Так ше доставаю два шори бинарних цифрох, означме их зоз a_1, \ldots, a_k и b_1, \ldots b_k. Потим ше за кажду позицию i \in {1, \ldots, k } рахує c_i з помоцу шлїдуюцих правилох:

За a_{i} = 0, b_{i} = 0 важи c_{i} = 0
За a_{i} = 0, b_{i} = 1 важи c_{i} = 1
За a_{i} = 1, b_{i} = 0 важи c_{i} = 1
За a_{i} = 1, b_{i} = 1 важи c_{i} = 0

Шлїд бинарних цифрох c_1, \ldots, c_k (хтори можебуц ма водзаци нули) то бинарни запис резултату, односно числа x \ \text{xor} \ y.

Оператор конюнкциї у Pascal-u означени зоз and, док го у C++ записуєме з помоцу симбола&. Тота операция x\ \text{and} \ y ше за нєнеґативни цали числа x,y дефинує на шлїдуюци способ. Перше ше числа запишу у бинарном запису. Кед же єдно число ма менєй цифри од другого, дописую му ше водзаци нули покля ше нє виєднача числа бинарних цифрох. Так ше доставаю два шлїди бинарних цифрох, означме их зоз a_1, \ldots, a_k и b_1, \ldots b_k.Потим ше за кажду позицию i \in \{1, \ldots, k \} рахує c_i з помоцу шлїдуюцих правилох: