An đang nghiên cứu các dãy nhị phân và phép toán AND trên bit. An có một dãy số nguyên dương và muốn tính phép AND bit của tất cả các phần tử trong một đoạn \([l, r]\).

Hãy giúp An viết chương trình xử lý nhanh các truy vấn.

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra kết quả phép AND bit trên một dòng.

Ví dụ

Input:

5 3
7 5 3 12 6
1 3
2 5
3 4

Output:

1
0
0