#2649. 别生气

别生气

题目描述

希蒙随手写了一个由 nn 个元素组成的数组 aa

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

现要做 qq 次查询。

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

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

输入描述

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

每个测试用例的第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n ( 1ai1091 \le a_i \le 10^9 ) 表示数组 aa 的元素。

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

每个测试用例的下一行 qq 包含两个数字: llrr1lrn1 \le l \le r \le n)表示子段的左边界和右边界 。

保证所有测试用例中 nn 的总和不超过 21052 \cdot 10^5 。同时,保证所有测试用例的 qq 之和不超过 21052 \cdot 10^5

输出描述

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

样例描述

输入

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

输出

0
0
34