题目描述

希蒙随手写了一个由 $n$ 个元素组成的数组 $a$ 。

其中定义 $f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$ （这里 $\&$ 表示 位与运算）

现要做 $q$ 次查询。

每个查询由 $l$ 和 $r$ 这两个数字组成，需要计算出 $f(l, r)$ 的值。

如果希蒙没有及时解决这个问题，程老师就会找他麻烦。

输入描述

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2 \cdot 10^5$ ) 表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^9$ ) 表示数组 $a$ 的元素。

每个测试用例的第三行都包含一个整数 $q$ ( $1 \le q \le 10^5$ ) - 表示查询次数。

每个测试用例的下一行 $q$ 包含两个数字： $l$ 和 $r$ （ $1 \le l \le r \le n$）表示子段的左边界和右边界 。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。同时，保证所有测试用例的 $q$ 之和不超过 $2 \cdot 10^5$ 。

输出描述

为每个查询输出$f(l,r)$的值.

样例描述

输入

5
15 14 17 42 34
3
1 5
2 3
4 5

输出

0
0
34