is a working-class citizen, he works for company H(Heinz). One day, wants to know how much his coworkers like him.
After some research, organized the results into a string

1. when , this means that the -th worker likes Fish.
2. when , this means that the -th worker dislikes Fish.

After researching， copied down as a new string ，and saw that there were many 0s among , he became very sad. So he wished to insert some to any position of in order to make himself happier.
If the length of is after inserts， would become sad under either of the following two conditions:

1. there exists a which the number of 0 are strictly larger than the number of 1 within to .
2. there exists a which the number of 0 are strictly larger than the number of 1 within to .

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

The first line contains two integers  denoting the numbers of colleagues and questions.
The second line contains a string .
For the next  lines, each line contains two integers , , requesting the least number of changes if =.

To reduce the impact of output time, you only need to output the  of each query.

10 5
0001001111
1 6
1 10
5 7
4 7
4 6

0

For the example, the answers are .
the possible solutions are:
000100->10101010101
0001001111->11100010101111
001->10101
1001->10101
100->10101