题目描述
希蒙随手写了一个由 n 个元素组成的数组 a 。
其中定义 f(l,r)=al & al+1 &…& ar (这里 & 表示 位与运算)
现要做 q 次查询。
每个查询由 l 和 r 这两个数字组成,需要计算出 f(l,r) 的值。
如果希蒙没有及时解决这个问题,程老师就会找他麻烦。
输入描述
每个测试用例的第一行包含一个整数 n ( 1≤n≤2⋅105 ) 表示数组 a 的长度。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an ( 1≤ai≤109 ) 表示数组 a 的元素。
每个测试用例的第三行都包含一个整数 q ( 1≤q≤105 ) - 表示查询次数。
每个测试用例的下一行 q 包含两个数字: l 和 r ( 1≤l≤r≤n)表示子段的左边界和右边界 。
保证所有测试用例中 n 的总和不超过 2⋅105 。同时,保证所有测试用例的 q 之和不超过 2⋅105 。
输出描述
为每个查询输出f(l,r)的值.
样例描述
输入
5
15 14 17 42 34
3
1 5
2 3
4 5
输出
0
0
34