Đề bài

Cho một mảng nhị phân gồm N phần tử, mỗi phần tử chỉ nhận giá trị 0 hoặc 1.

Có Q truy vấn, mỗi truy vấn yêu cầu đếm số lượng số 1 trong đoạn [l, r].

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q.

Dòng thứ hai chứa N số 0 hoặc 1.

Q dòng tiếp theo chứa hai số l và r.

Dữ liệu ra

Với mỗi truy vấn, in ra số lượng số 1 trong đoạn.

Giới hạn

1 ≤ N, Q ≤ 2×10⁵

Ví dụ

Input

8 3
1 0 1 1 0 0 1 1
1 4
3 7
5 8

Output

3
3
2