B. Lovely Fish
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

$$$Fish$$$ is a working-class citizen, he works for company H(Heinz). One day, $$$Fish$$$ wants to know how much his coworkers like him.

After some research, $$$Fish$$$ organized the results into a string $$$S$$$

  1.  when $$$S_{i}=1$$$, this means that the $$$i$$$th worker likes Fish.
  2.  when $$$S_{i}=0$$$, this means that the $$$i$$$th worker dislikes Fish.

After researching，$$$Fish$$$ copied down $$$S_{l...r}$$$ as a new string $$$T$$$，and saw that there were many 0s among $$$T$$$, he became very sad. So he wished to insert some $$$1$$$ to any position of $$$T$$$ in order to make himself happier.

If the length of $$$T$$$ is $$$m$$$ after inserts，$$$Fish$$$ would become sad under either of the following two conditions:

  1.  there exists a $$$p~(1\leq p \leq m)$$$ which the number of 0 are strictly larger than the number of 1 within $$$T_1$$$ to $$$T_p$$$.
  2.  there exists a $$$p~(1\leq p \leq m)$$$ which the number of 0 are strictly larger than the number of 1 within $$$T_p$$$ to $$$T_m$$$.

$$$Fish$$$ also doesn't know for certain the value of $$$l$$$ and $$$r$$$, so he wants to know with $$$q$$$ possible pairs of $$$l$$$ and $$$r$$$, the least number of inserts that Fish needs to make in order to make himself happy.

Input

The first line contains two integers $$$n, q~(1 \leq n,q \leq 1,000,000)$$$ denoting the numbers of colleagues and questions.

The second line contains a string $$$S$$$.

for the next $$$q$$$ lines, each line contains two integers $$$l_i$$$, $$$r_i$$$, requesting the least number of changes if $$$T$$$=$$$S_{l...r}$$$

Output

To reduce the impact of output time, you only need to output the $$$\texttt{XOR}$$$ of each query.

Example
Input
10 5
0001001111
1 6
1 10
5 7
4 7
4 6
Output
0
Note

For the example, the answers are $$$5,4,2,1,2$$$.

the possible solutions are:

000100->10101010101

0001001111->11100010101111

001->10101

1001->10101

100->10101