焰与霜的共鸣
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

        在 Surtr 的记忆中，存在着大量彼此矛盾的片段——某些发生在雪原，某些在城市，有的甚至不属于已知的任何地理坐标。
        Surtr的记忆可以被量化为一列整数序列 S = \{a_1, a_2, \dots, a_n\}。
        每个整数代表一个“记忆节点”的能量波动。不同的区间 [\ell, r]，对应着不同阶段的情绪与记忆片段。当 Surtr 集中注意力时，会将这些片段重组，形成无数种可能的“记忆组合”。
        每一个记忆组合都能产生特定的“共鸣值”，某种隐藏的极值模式存在于这些记忆片段之间，我们需要找到这种极值模式。

为了研究这种极值模式，我们将数据形式化为以下模型：

设整数序列（或多重集合）S = \{ a_1, a_2, \dots, a_n \}.
对任意下标区间 (1 \le \ell \le r \le n)，定义区间多重集合 S_{\ell, r} = \{ a_\ell, a_{\ell+1}, \dots, a_r \}.
由 S_{\ell, r} 的所有非空子集（这里子集按多重集合定义，即对每个元素可取或不取）产生的子集和集合记为：

T_{\ell, r} = \left\{ \sum_{x \in U} x \;\middle|\; U \subseteq S_{\ell, r},U\neq \varnothing\right\}.

（注意：若 S_{\ell, r} 含重复元素，则不同的选择可能产生相同的和，T_{\ell, r} 作为集合只保留不同的和。）

对任意集合 X 定义：
        1. \operatorname{mex} 运算：\operatorname{mex}(X) = \min \{ k \in \mathbb{N} \mid k \notin X \}.
        2. \gcd 运算：\gcd(X) = \gcd(x_1, x_2, \dots, x_k), \quad \text{若 } X = \{x_1, \dots, x_k\}.

令 R 为 T_{\ell, r} 的任一非空子集，即 R \subseteq T_{\ell, r}, \quad R \neq \varnothing.
给定 q 次查询，每次查询给出一个区间 [\ell, r]，每次查询的答案为：

\max_{ \substack{R \subseteq T_{\ell, r} \\ R \neq \varnothing}}<br />\big( \operatorname{mex}(R) \oplus \gcd(R) \big).
 其中 “\oplus” 表示按位异或运算。

【名词解释】
        1. \mathrm{mex}:整数数组的 \mathrm{mex} 定义为没有出现在数组中的最小非负整数。例如：\mathrm{mex}(\{1,2,3\}) = 0、\mathrm{mex}(\{0,2,2,5\}) = 1
        2. \mathrm{gcd} ：即最大公因数，指多个整数共有因数中最大的一个。例如，12、18 和 30 的公因数有 1, 2, 3, 6， 其中最大的因数是 6，因此 \mathrm{gcd}(12, 18, 30) = 6. 注意： \mathrm{gcd}(x) = x，\mathrm{gcd}(0,x)=x. 特别地，定义 \mathrm{gcd}(0,0)=0 .
        3. \oplus 代表按位异或。对两个整数的二进制表示按位进行异或运算，只有两个对应位不同时才为 1。例如：5 \oplus 6 = (101)_2\oplus(110)_2 = (011)_2= 3

输入描述:

第一行，输入一个正整数 n (1\le n\le 1\times10^5)，代表整数序列的长度。
第二行，输入 n 个整数 a_1, a_2, \dots, a_n(0\le a_i\le 1\times10^9，\sum a\le 1\times10^9），表示整数序列。
第三行，输入一个正整数q (1\le q\le 1\times10^5)，代表一共有 q 次查询。
接下来 q 行，每行两个正整数 l,r (1\le l\le r \le n)，查询区间[l,r]的 “极值模式”(详细查询内容见题面)。

输出描述:

输出共 q 行，每行输出一个整数，代表每次查询的结果。
示例1

输入

复制 
4
0 1 2 1
3
1 4
1 3
1 1

输出

复制 
5
5
1

说明

样例解释：
对于第一次查询，S_{1, 4} = \{ 0，1，2，1 \}，其子集有\{0\}，\{1\}，\{2\}，\{0，1\}，\{0，2\}，\{1,1\}，
\{1，2\}，\{0，1，2\}，\{1，1，2\}，\{0，1，1，2\}.这些子集产生的和有0，1，2，3，4 这五种情况，故而 T_{1, 4} = \{ 0，1，2，3 ，4\}，一种最优的子集选择方案是 R = \{0,4\}，此时 \operatorname{mex}(\{0,4\}) \oplus \gcd(\{0,4\}) = 1\oplus4=5.

对于第二次查询，S_{1, 3} = \{ 0，1，2 \}，T_{1, 3} = \{ 0，1，2，3 \}，一种最优的子集选择方案是 R = \{0，1，2，3\}，此时 \operatorname{mex}(\{0，1，2，3\}) \oplus \gcd(\{0，1，2，3\}) = 4\oplus1=5.

对于第三次查询，S_{1, 1} = \{ 0 \}，T_{1, 1} = \{ 0\}，一种最优的子集选择方案是 R = \{0\}，此时 \operatorname{mex}(\{0\}) \oplus \gcd(\{0\}) = 1\oplus0=1.
示例2

输入

复制 
3
0 2 4
4
1 3
1 1
2 2
3 3

输出

复制 
7
1
2
4