binarray

Task

You are given a string of length $n$ which is made of digits $0$ and $1$. Because it's summer and you want to relax after the contest, the statement will be short and simple:

You have to process $q$ queries. For each query, you will have to find how many subarrays of the subarray $[L, R]$ have the property that if we apply the bitwise OR operation, we will obtain $1$.

For example, if $s = 1001101$ and one of the queries contains the range $[2, 6]$, the subarray for which we will have to count the valid subarrays will be $00110$. In this subarray, three of the subarrays which respect the given property are $01$, $110$ și $00110$. However, $00$ does not respect the given property.

The problem setting team managed to solve the problem with the speed of the closed light, so it's now your turn to do it, when the lights are on.

Input data

The first line of the input contains $n$, the length of the string. The next line contains $s$, the string of length $n$ containing only $0$s and $1$s.

The third line of the input contains $q$, the number of queries. The next $q$ lines contain $L_i$ and $R_i$, the ends of the substrings we need to find the answers for.

Output data

You will print $q$ lines, the $i^{th}$ line containing the answer for the $i^{th}$ query.

Constraints and clarifications

• $1 \leq n, q \leq 4 \ 000 \ 000$;

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);

Example

stdin

12
011110000010
9
3 10
4 10
4 11
5 5
8 10
1 8
10 11
3 7
6 6

stdout

21
13
21
1
0
29
2
12
0