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.
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.
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?
In the third query, the number in binary is $1010101011$, which is represented in decimal as $683$ so the answer is $3$.
101010101110101 5 1 3 1 4 1 10 8 10 8 15
5 0 3 3 7
There are 2 solutions:
Use segment tree to get the range sum with mod 10.