Chưng và Quýt là hai người bạn thân, cùng nhau khám phá thế giới kỳ lạ của Kiệt, nơi mọi thứ đều được mã hóa bằng những chuỗi nhị phân chỉ gồm 0 và 1. Một ngày nọ, Kiệt đưa cho họ một dãy ký tự nhị phân dài n và đặt ra cho hai bạn một thử thách không hề đơn giản. Bên cạnh dãy ký tự ấy, Kiệt còn đưa ra q câu hỏi, mỗi câu hỏi là một đoạn liên tiếp [l, r] trong dãy.

Với mỗi đoạn được hỏi, Chưng và Quýt phải cùng nhau quan sát tất cả các đoạn con nằm hoàn toàn trong đoạn [l, r]. Kiệt gọi một đoạn con là đẹp nếu trong đó số lượng bit 1 bằng đúng số lượng bit 0.

Nhiệm vụ của hai bạn là: Với mỗi truy vấn, hãy tính tổng độ dài của tất cả các đoạn con đẹp trong đoạn [l, r].. Thử thách này không hề dễ dàng, bởi Kiệt đưa ra những giới hạn rất lớn, là một người bạn của hai người bạn hãy giúp họ giải quyết bài toán này nhé!!

Input

• Dòng đầu tiên gôm hai số ~n~ và ~q~ với (~\leq n, q \le2e5 ~) là độ dài chuỗi và số lượng truy vấn.
• ~q~ dòng tiếp theo mỗi dòng gồm hai số ~[l, r]~ với (~1\leq l \leq r \leq n~)

Output In ra ~q~ dòng, mỗi dòng chứa một số nguyên là kết quả sau mỗi truy vấn

Subtask

Sample Input 1

6 3
101001
3 6
5 6
1 6

Sample Output 1

8
2
22

Giải thích:

Ở truy vấn [3, 6] ta sẽ có những đoạn đẹp là đoạn [3, 4], [5, 6] và [3, 6] tổng độ dài 3 đoạn này là: 2 + 2 + 4 = 8