{"raw_statement":[{"iden":"statement","content":"For an array $b$ of length $m$ we define the function $f$ as\n\n<center>$f(b) = \\begin{cases} b[1] &amp; \\quad \\text{if } m = 1 \\\\ f(b[1] \\oplus b[2],b[2] \\oplus b[3],\\dots,b[m-1] \\oplus b[m]) &amp; \\quad \\text{otherwise,} \\end{cases}$</center>where $\\oplus$ is [bitwise exclusive OR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).\n\nFor example, $f(1,2,4,8)=f(1\\oplus2,2\\oplus4,4\\oplus8)=f(3,6,12)=f(3\\oplus6,6\\oplus12)=f(5,10)=f(5\\oplus10)=f(15)=15$\n\nYou are given an array $a$ and a few queries. Each query is represented as two integers $l$ and $r$. The answer is the maximum value of $f$ on all continuous subsegments of the array $a_l, a_{l+1}, \\ldots, a_r$."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\le n \\le 5000$) — the length of $a$.\n\nThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($0 \\le a_i \\le 2^{30}-1$) — the elements of the array.\n\nThe third line contains a single integer $q$ ($1 \\le q \\le 100\\,000$) — the number of queries.\n\nEach of the next $q$ lines contains a query represented as two integers $l$, $r$ ($1 \\le l \\le r \\le n$)."},{"iden":"output","content":"Print $q$ lines — the answers for the queries."},{"iden":"examples","content":"Input\n\n3\n8 4 1\n2\n2 3\n1 2\n\nOutput\n\n5\n12\n\nInput\n\n6\n1 2 4 8 16 32\n4\n1 6\n2 5\n3 4\n1 2\n\nOutput\n\n60\n30\n12\n3"},{"iden":"note","content":"In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.\n\nIn second sample, optimal segment for first query are $[3,6]$, for second query — $[2,5]$, for third — $[3,4]$, for fourth — $[1,2]$."}],"translated_statement":[{"iden":"statement","content":"对于长度为 $m$ 的数组 $b$，我们定义函数 $f$ 为 \n\n其中 $plus.circle$ 表示按位异或。\n\n例如，$f (1, 2, 4, 8) = f (1 plus.circle 2, 2 plus.circle 4, 4 plus.circle 8) = f (3, 6, 12) = f (3 plus.circle 6, 6 plus.circle 12) = f (5, 10) = f (5 plus.circle 10) = f (15) = 15$\n\n给定一个数组 $a$ 和若干查询。每个查询由两个整数 $l$ 和 $r$ 表示，答案是数组 $a_l, a_{l + 1}, dots.h, a_r$ 的所有连续子段上 $f$ 的最大值。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 5000$) —— 数组 $a$ 的长度。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($0 lt.eq a_i lt.eq 2^(30) -1$) —— 数组的元素。\n\n第三行包含一个整数 $q$ ($1 lt.eq q lt.eq 100 thin 000$) —— 查询的数量。\n\n接下来的 $q$ 行每行包含一个查询，表示为两个整数 $l$, $r$ ($1 lt.eq l lt.eq r lt.eq n$)。\n\n请输出 $q$ 行 —— 每个查询的答案。\n\n在第一个样例中，两个查询的函数最大值均在等于整个区间的子段上取得。\n\n在第二个样例中，第一个查询的最优区间为 $[ 3, 6 ]$，第二个查询为 $[ 2, 5 ]$，第三个查询为 $[ 3, 4 ]$，第四个查询为 $[ 1, 2 ]$。"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 5000$) —— 数组 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$ ($0 lt.eq a_i lt.eq 2^(30) -1$) —— 数组的元素。第三行包含一个整数 $q$ ($1 lt.eq q lt.eq 100 thin 000$) —— 查询的数量。接下来的 $q$ 行每行包含一个查询，表示为两个整数 $l$, $r$ ($1 lt.eq l lt.eq r lt.eq n$)。"},{"iden":"output","content":"请输出 $q$ 行 —— 每个查询的答案。"},{"iden":"examples","content":"输入\n3\n8 4 1\n2\n2 3\n1 2\n输出\n5\n12\n\n输入\n6\n1 2 4 8 16 32\n4\n1 6\n2 5\n3 4\n1 2\n输出\n60\n30\n12\n3"},{"iden":"note","content":"在第一个样例中，两个查询的函数最大值均在等于整个区间的子段上取得。在第二个样例中，第一个查询的最优区间为 $[ 3, 6 ]$，第二个查询为 $[ 2, 5 ]$，第三个查询为 $[ 3, 4 ]$，第四个查询为 $[ 1, 2 ]$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ a = (a_1, a_2, \\dots, a_n) $ be an array of integers, where $ a_i \\in \\mathbb{Z} $ and $ 0 \\le a_i < 2^{30} $.  \nFor a subarray $ b = (b_1, b_2, \\dots, b_m) $, define the function $ f(b) $ recursively as:  \n- If $ m = 1 $, then $ f(b) = b_1 $.  \n- If $ m > 1 $, then $ f(b) = f(b_1 \\oplus b_2, b_2 \\oplus b_3, \\dots, b_{m-1} \\oplus b_m) $,  \nwhere $ \\oplus $ denotes bitwise XOR.\n\n**Constraints**  \n1. $ 1 \\le n \\le 5000 $  \n2. $ 0 \\le a_i < 2^{30} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\le q \\le 100000 $  \n4. For each query $ (l, r) $: $ 1 \\le l \\le r \\le n $\n\n**Objective**  \nFor each query $ (l, r) $, compute:  \n$$\n\\max_{l \\le i \\le j \\le r} f(a_i, a_{i+1}, \\dots, a_j)\n$$","simple_statement":null,"has_page_source":false}