Task
You are given a string of length which is made of digits and . Because it's summer and you want to relax after the contest, the statement will be short and simple:
You have to process queries. For each query, you will have to find how many subarrays of the subarray have the property that if we apply the bitwise OR operation, we will obtain .
For example, if and one of the queries contains the range , the subarray for which we will have to count the valid subarrays will be . In this subarray, three of the subarrays which respect the given property are , și . However, 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 , the length of the string. The next line contains , the string of length containing only s and s.
The third line of the input contains , the number of queries. The next lines contain and , the ends of the substrings we need to find the answers for.
Output data
You will print lines, the line containing the answer for the query.
Constraints and clarifications
- ;
# | Score | Constraints |
---|---|---|
1 | 7 | |
2 | 13 | |
3 | 36 | |
4 | 14 | |
5 | 30 |
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