「KDOI-06-S」签到题

你正在追番，突然家长进来了，于是你假装在写一道数据结构题。

定义一个长度为 $m$ 的数组 $v$ 是合法的，当且仅当经过若干次以下操作可以使 $v$ 中的所有元素相等： * 选择四个整数 $a,b,c,d$（$1\leq a\leq b\leq m$，$1\leq c\leq d\leq m$）满足 $b-a+1=d-c+1$，且 $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$，其中 $\operatorname{or}$ 表示按位或运算。接下来，将区间 $[a,b]$ 的数**复制下来再覆盖**到区间 $[c,d]$。**注意：区间 $\bm{[a,b]}$ 和 $\bm{[c,d]}$ 可能会相交。** 给出一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$ 以及 $q$ 次询问，每次询问给定两个正整数 $l,r$，你需要回答区间 $[l,r]$ 内的最长合法子区间的长度。

从标准输入读入数据。 **本题含有多组测试数据。** 输入的第一行包含两个整数 $T,id$，表示数据组数和测试点编号（样例的测试点编号为 $0$）。 对于每组测试数据数据，第一行两个正整数 $n,q$，表示序列长度与询问次数。 第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示序列 $a$ 中每个元素的值。 接下来 $q$ 行，每行两个正整数 $l,r$，表示询问的区间。

输出到标准输出。 对于每组测试数据的每次询问，输出一行一个整数，表示区间 $[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

**【样例解释 #1】** 对于第一组数据的第一个询问，最长的合法子区间为 $[1,7]$，以下是一种可能的操作序列： 1. 选择区间 $[1,4]$ 和 $[2,5]$，将区间 $[1,4]$ 中的数**先复制**下来，再覆盖到 $[2,5]$ 上，此时序列变为 $[0,0,4,2,6,6,6]$。 2. 选择区间 $[5,6]$ 和 $[3,4]$，此时序列变为 $[0,0,6,6,6,6,6]$。 3. 选择区间 $[4,7]$ 和 $[1,4]$，此时序列变为 $[6,6,6,6,6,6,6]$。 注意，操作**并不会**真正的修改原序列中的值。 对于第一组数据的第二个询问，最长的合法子区间为 $[2,2]$ 和 $[3,3]$。 **【样例 #2】** 见选手目录下的 `binary/binary2.in` 与 `binary/binary2.ans`。 这个样例满足测试点 $5\sim 8$ 的条件限制。 **【样例 #3】** 见选手目录下的 `binary/binary3.in` 与 `binary/binary3.ans`。 这个样例满足测试点 $25\sim 31$ 的条件限制。 **【样例 #4】** 见选手目录下的 `binary/binary4.in` 与 `binary/binary4.ans`。 这个样例满足测试点 $46\sim 50$ 的条件限制。 *** **【数据范围】** 对于所有数据保证：$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}$。 | 测试点编号 | $\sum n\le$ | $\sum q\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $5$ | 无 | | $2\sim 4$ | $100$ | $100$ | 无 | | $5\sim 8$ | $1000$ | $1000$ | 无 | | $9\sim 14$ | $1000$ | $10^6$ | 无 | | $15\sim 19$ | $6000$ | $10^6$ | 无 | | $20\sim 24$ | $50000$ | $10$ | 无 | | $25\sim 31$ | $10^5$ | $10^5$ | B | | $32\sim 36$ | $2\times 10^5$ | $2\times 10^5$ | 无 | | $37\sim 41$ | $5\times 10^5$ | $10^6$ | B | | $42\sim 44$ | $5\times 10^5$ | $5\times 10^5$ | 无 | | $45$ | $2\times 10^6$ | $2\times 10^6$ | A | | $46\sim 50$ | $2\times 10^6$ | $2\times 10^6$ | 无 | + 特殊性质 A：保证序列 $a$ 中的每个数均在 $[0,2^{30})$ 之间均匀随机生成。 + 特殊性质 B：保证对于任意 $1\le i\le n$，$a_i\le 3$。 *** **【提示】** 本题输入输出量较大，请使用适当的 I/O 方式。 **请注意常数因子对程序运行效率产生的影响。** KDOI 出题组温馨提示：**多测不清空，爆零两行泪。**