Given a binary string S of 0s and 1s of length N and M queries of the type [l, r], find the number of substrings of S(l to r) where there are even 1s.

Constraints:

N <= 10^5

M <= 10^5

1 <= l <= r <= N

Sample Input:

N = 5

S = 10001

M = 2

2 4

3 5

Sample Output:

6

3

Explanation:

For [2, 4] the 6 valid substrings are [2,2], [2,3], [2,4], [3,3], [3,4], [4,4]

For [3, 5] the 3 valid substrings are [3,3], [3,4], [4,4]