P9747 “KDOI-06-S” Check-in Problem.

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

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]$.

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.

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]$.

**[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}$. | Test Point ID | $\sum n\le$ | $\sum q\le$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $5$ | None | | $2\sim 4$ | $100$ | $100$ | None | | $5\sim 8$ | $1000$ | $1000$ | None | | $9\sim 14$ | $1000$ | $10^6$ | None | | $15\sim 19$ | $6000$ | $10^6$ | None | | $20\sim 24$ | $50000$ | $10$ | None | | $25\sim 31$ | $10^5$ | $10^5$ | B | | $32\sim 36$ | $2\times 10^5$ | $2\times 10^5$ | None | | $37\sim 41$ | $5\times 10^5$ | $10^6$ | B | | $42\sim 44$ | $5\times 10^5$ | $5\times 10^5$ | None | | $45$ | $2\times 10^6$ | $2\times 10^6$ | A | | $46\sim 50$ | $2\times 10^6$ | $2\times 10^6$ | None | - 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