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\). Với mỗi câu hỏi, hãy tính giá trị bitwise OR của các phần tử trong đoạn từ \(L\) đến \(R\): \(A_L \text{ or } A_{L+1} \text{ or } \dots \text{ or } A_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, R_i\) đại diện cho một câu hỏi.

Output

• Gồm \(M\) dòng, mỗi dòng là kết quả của phép toán bitwise OR tương ứng với từng câu hỏi.

Constraints

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

Example

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

63
63
2