The annual Robo Race has begun!
The race consists of $Q$ rounds taking place in a $2 \times N$ obstacle course.
For round $i$, every Robo begins at the cell $(2,L_i)$ and races to the cell $(2,R_i)$.
Note that the starting and ending square will never have an obstacle.
An example of the obstacle course is shown in the following figure:

_{Credits to Hong Kong Olympiad in Informatics Organizing Committee}

To increase your winning chances, you had installed jet engines to your Robo!
This allows the Robo to travel to the right in negligible time, and it only takes 1 unit of time to travel up and down.

You would like to figure out the minimum amount of time for your Robo to complete the obstacle course every round.
It is guaranteed that it is possible to reach the end every round.

Input

The first line contains two integers $N,Q$.
The next 2 lines contains a string of length $N$, describing the initial obstacle course. Obstacles are represented by $1$, and empty spaces is represented by $0$.
The next $Q$ lines contain two integers $L_i, R_i$.

Output

Output $Q$ integers: the minimum time to complete the obstacle course, one per line.

Constraints

For all subtasks:

• $1 \le N, Q \le 10^5$
• $1 \le L_i \le R_i \le N$

Subtask 1 (10%): $Q=1, L_i = 1, R_i = N$
Subtask 2 (20%): $N,Q \le 1000$
Subtask 3 (30%): For all $1\le i \le Q$, $L_i = 1$
Subtask 4 (40%): No additional constraints