{"raw_statement":[{"iden":"background","content":"你正在追番，突然家长进来了，于是你假装在写一道数据结构题。\n\n"},{"iden":"statement","content":"定义一个长度为 $m$ 的数组 $v$ 是合法的，当且仅当经过若干次以下操作可以使 $v$ 中的所有元素相等：\n\n* 选择四个整数 $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\n给出一个长度为 $n$ 的序列 $a_1,a_2,\\ldots,a_n$ 以及 $q$ 次询问，每次询问给定两个正整数 $l,r$，你需要回答区间 $[l,r]$ 内的最长合法子区间的长度。"},{"iden":"input","content":"从标准输入读入数据。\n\n**本题含有多组测试数据。**\n\n输入的第一行包含两个整数 $T,id$，表示数据组数和测试点编号（样例的测试点编号为 $0$）。\n\n对于每组测试数据数据，第一行两个正整数 $n,q$，表示序列长度与询问次数。\n\n第二行 $n$ 个正整数 $a_1,a_2,\\ldots,a_n$，表示序列 $a$ 中每个元素的值。\n\n接下来 $q$ 行，每行两个正整数 $l,r$，表示询问的区间。"},{"iden":"output","content":"输出到标准输出。\n\n对于每组测试数据的每次询问，输出一行一个整数，表示区间 $[l,r]$ 内的最长合法子区间的长度。"},{"iden":"note","content":"**【样例解释 #1】**\n\n对于第一组数据的第一个询问，最长的合法子区间为 $[1,7]$，以下是一种可能的操作序列：\n\n1. 选择区间 $[1,4]$ 和 $[2,5]$，将区间 $[1,4]$ 中的数**先复制**下来，再覆盖到 $[2,5]$ 上，此时序列变为 $[0,0,4,2,6,6,6]$。\n\n2. 选择区间 $[5,6]$ 和 $[3,4]$，此时序列变为 $[0,0,6,6,6,6,6]$。\n\n3. 选择区间 $[4,7]$ 和 $[1,4]$，此时序列变为 $[6,6,6,6,6,6,6]$。\n\n注意，操作**并不会**真正的修改原序列中的值。\n\n对于第一组数据的第二个询问，最长的合法子区间为 $[2,2]$ 和 $[3,3]$。\n\n**【样例 #2】**\n\n见选手目录下的 `binary/binary2.in` 与 `binary/binary2.ans`。\n\n这个样例满足测试点 $5\\sim 8$ 的条件限制。\n\n**【样例 #3】**\n\n见选手目录下的 `binary/binary3.in` 与 `binary/binary3.ans`。\n\n这个样例满足测试点 $25\\sim 31$ 的条件限制。\n\n**【样例 #4】**\n\n见选手目录下的 `binary/binary4.in` 与 `binary/binary4.ans`。\n\n这个样例满足测试点 $46\\sim 50$ 的条件限制。\n\n***\n\n**【数据范围】**\n\n对于所有数据保证：$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}$。\n\n| 测试点编号 | $\\sum n\\le$ | $\\sum q\\le$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $5$ | $5$ | 无 |\n| $2\\sim 4$ | $100$ | $100$ | 无 |\n| $5\\sim 8$ | $1000$ | $1000$ | 无 |\n| $9\\sim 14$ | $1000$ | $10^6$ | 无 |\n| $15\\sim 19$ | $6000$ | $10^6$ | 无 |\n| $20\\sim 24$ | $50000$ | $10$ | 无 |\n| $25\\sim 31$ | $10^5$ | $10^5$ | B |\n| $32\\sim 36$ | $2\\times 10^5$ | $2\\times 10^5$ | 无 |\n| $37\\sim 41$ | $5\\times 10^5$ | $10^6$ | B |\n| $42\\sim 44$ | $5\\times 10^5$ | $5\\times 10^5$ | 无 |\n| $45$ | $2\\times 10^6$ | $2\\times 10^6$ | A |\n| $46\\sim 50$ | $2\\times 10^6$ | $2\\times 10^6$ | 无 |\n\n+ 特殊性质 A：保证序列 $a$ 中的每个数均在 $[0,2^{30})$ 之间均匀随机生成。\n+ 特殊性质 B：保证对于任意 $1\\le i\\le n$，$a_i\\le 3$。\n\n***\n\n**【提示】**\n\n本题输入输出量较大，请使用适当的 I/O 方式。\n\n**请注意常数因子对程序运行效率产生的影响。**\n\nKDOI 出题组温馨提示：**多测不清空，爆零两行泪。**"}],"translated_statement":null,"sample_group":[["2 0\n7 2\n0 4 2 6 0 6 6\n1 7\n2 3\n3 1\n1 2 3\n1 3","7\n1\n3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}