binarray

Time limit: 3s Memory limit: 256MB Input: Output:

Task

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

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

For example, if s=1001101s = 1001101 and one of the queries contains the range [2,6][2, 6], the subarray for which we will have to count the valid subarrays will be 0011000110. In this subarray, three of the subarrays which respect the given property are 0101, 110110 și 0011000110. However, 0000 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 nn, the length of the string. The next line contains ss, the string of length nn containing only 00s and 11s.

The third line of the input contains qq, the number of queries. The next qq lines contain LiL_i and RiR_i, the ends of the substrings we need to find the answers for.

Output data

You will print qq lines, the ithi^{th} line containing the answer for the ithi^{th} query.

Constraints and clarifications

  • 1n,q4 000 0001 \leq n, q \leq 4 \ 000 \ 000;
# Score Constraints
1 7 1n,q1001 \leq n, q \leq 100
2 13 1n,q2 0001 \leq n, q \leq 2 \ 000
3 36 1n,q200 0001 \leq n, q \leq 200 \ 000
4 14 1n,q1 000 0001 \leq n, q \leq 1 \ 000 \ 000
5 30 1n,q4 000 0001 \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

Log in or sign up to be able to send submissions!