Binarithm

Time Limit: 2000ms

Memory Limit: 256MB

Q - Binarithm

Submissions Submit

Ali loves programming. One day he decided to make a large project to impress his professors. 
As he is a good software engineer, he wanted it to occupy the least number of gigabytes, so he considered using binary files instead of ASCII files. The data in binary files are stored as a string of bits.
Ali finished his project and wants to view the binary file he wrote. As you may know, it cannot be viewed in a human-readable format (characters), so he got stuck. 
Can you help Ali by telling him what is the first digit from right in decimal representation of a range $l$ to $r$ of bits in his binary file?
Note: Ali is so annoying, so he wants to ask a lot of questions.

Input

The first line contains a string of binary digits $s$ ($1 \le |s| \le 2 \cdot 10^5$).
The second line contains an integer $q$ ($1 \le q \le 2 \cdot 10^5$)  --- the number of queries.
Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le |s|$)  --- the $i$-th number in binary.

Output

For each query ,print an integer representing  the first digit from right in decimal representation of a range  $l_i$ to $r_i$ of bits in his binary file? 

Notes

In the third query, the number in binary is $1010101011$, which is represented in decimal as $683$ so the answer is $3$.

Samples

Input	Output
101010101110101 5 1 3 1 4 1 10 8 10 8 15 Copy	5 0 3 3 7 Copy

There are 2 solutions: 
First solution:
Notice that powers of 2 mod 10 cycle every fourth power starting from 2^1:  2^0 = 1 (that is an exception) 
2^1 % 10 = 2^5 % 10 = 2^9 % 10 = ... = 2^(1+4x) = ... = 2 
2^2 % 10 = 2^6 % 10 = 2^10 % 10 = ... = 2^(2+4x) = ... = 4 
2^3 % 10 = 2^7 % 10 = 2^11 % 10 = ... = 2^(3+4x) = ... = 8 
2^4 % 10 = 2^8 % 10 = 2^12 % 10 = ... = 2^(4+4x) = ... = 6 ; where x is a natural number (integers in [0, INF)).
Construct 4 prefix sums (frequencies): Prefix sum on the number of 1's in indices such that idx % 4 = 0. 
Prefix sum on the number of 1's in indices such that idx % 4 = 1. 
Prefix sum on the number of 1's in indices such that idx % 4 = 2. 
Prefix sum on the number of 1's in indices such that idx % 4 = 3. 
Using these 4 prefix sums we can get the first digit with the help of the observation above. One can process every query as follows: If there is a 1 at index R, it is counted. 
Let's assume idx[] contains the indices that are away from index R by 1, 5, 9, ..., 1+4x indices. We should get the number of ones in indices of idx[] and multiply the count by 2. That should give us the contribution of those indices to the constructed number. We can also remove the contribution of indices that are to the left of L.
Step 2 is repeated for different possible mods as explained in observations 3, 4, and 5 (For example, be sure to replace 1+4x with 2+4x and 2 with 4 as described in observation 3). 
Second solution:
Use segment tree to get the range sum with mod 10.