Background

You are watching anime, and suddenly your parents come in, so you pretend you are solving a data structure problem.

Problem Description

Define an array $v$ of length $m$ to be valid if and only if, after performing the following operation some number of times, all elements in $v$ can be made equal:

• Choose four integers $a,b,c,d$ ($1\leq a\leq b\leq m$, $1\leq c\leq d\leq m$) such that $b-a+1=d-c+1$, and$$v_a\operatorname{~or~}v_{a+1}\operatorname{~or~}\cdots\operatorname{~or~}v_b=v_c\operatorname{~or~}v_{c+1}\operatorname{~or~}\cdots\operatorname{~or~}v_d,$$where $\operatorname{or}$ denotes the bitwise OR operation. Then, copy the numbers in interval $[a,b]$ and overwrite them onto interval $[c,d]$. Note: intervals $\bm{[a,b]}$ and $\bm{[c,d]}$ may overlap.

You are given a sequence $a_1,a_2,\ldots,a_n$ of length $n$ and $q$ queries. Each query gives two positive integers $l,r$. You need to answer the length of the longest valid sub-interval within $[l,r]$.

Input Format

Read from standard input.

This problem contains multiple test cases.

The first line contains two integers $T,id$, representing the number of test cases and the test point ID (the sample’s test point ID is $0$).

For each test case, the first line contains two positive integers $n,q$, representing the sequence length and the number of queries.

The second line contains $n$ positive integers $a_1,a_2,\ldots,a_n$, representing the values of the sequence $a$.

The next $q$ lines each contain two positive integers $l,r$, representing the query interval.

Output Format

Write to standard output.

For each query in each test case, output one integer per line, representing the length of the longest valid sub-interval within $[l,r]$.

2 0
7 2
0 4 2 6 0 6 6
1 7
2 3
3 1
1 2 3
1 3

7
1
3

Hint

[Sample Explanation #1]

For the first query of the first test case, the longest valid sub-interval is $[1,7]$. One possible sequence of operations is:

1. Choose intervals $[1,4]$ and $[2,5]$. First copy the numbers in $[1,4]$, then overwrite them onto $[2,5]$. The sequence becomes $[0,0,4,2,6,6,6]$.

2. Choose intervals $[5,6]$ and $[3,4]$. The sequence becomes $[0,0,6,6,6,6,6]$.

3. Choose intervals $[4,7]$ and $[1,4]$. The sequence becomes $[6,6,6,6,6,6,6]$.

Note that the operations do not actually modify the values in the original sequence.

For the second query of the first test case, the longest valid sub-intervals are $[2,2]$ and $[3,3]$.

[Sample #2]

See binary/binary2.in and binary/binary2.ans in the contestant directory.

This sample satisfies the constraints of test points $5\sim 8$.

[Sample #3]

See binary/binary3.in and binary/binary3.ans in the contestant directory.

This sample satisfies the constraints of test points $25\sim 31$.

[Sample #4]

See binary/binary4.in and binary/binary4.ans in the contestant directory.

This sample satisfies the constraints of test points $46\sim 50$.

[Constraints]

It is guaranteed for all data that: $1\le T\le 2\times 10^5$, $1\le n,q,\sum n,\sum q\le 2\times 10^6$, $0\le a_i < 2^{30}$.

• Special Property A: Every number in sequence $a$ is generated uniformly at random within $[0,2^{30})$.
• Special Property B: For any $1\le i\le n$, $a_i\le 3$.

[Hint]

The input/output size of this problem is large. Please use an appropriate I/O method.

Please pay attention to the impact of constant factors on program runtime efficiency.

A warm reminder from the KDOI problemset team: If you do not clear your data between test cases, you will get zero points and cry for two lines.

Translated by ChatGPT 5