Cho dãy số \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Có \(M\) câu hỏi, mỗi câu hỏi gồm hai số nguyên \(L\) và \(R\), yêu cầu tính kết quả của phép toán bitwise AND cho tất cả các phần tử trong đoạn từ \(L\) đến \(R\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).
• Dòng thứ ba chứa số nguyên dương \(M\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) (\(1 \le L_i \le R_i \le N\)).

Output

• Gồm \(M\) dòng, mỗi dòng là kết quả của phép toán \(A_{L_i} \text{ AND } A_{L_i+1} \text{ AND } \dots \text{ AND } A_{R_i}\).

Example

5
34 23 12 34 2 
3
1 3
2 4
5 5

0
0
2

Constraints

• \(1 \le N, M \le 5 \cdot 10^5\)
• \(0 \le A_i \le 10^9\)