RoAlgo Contest #4 (incepatori) | poseidon

After FlaviuS mysteriously discovered that he is ambidextrous, he defined a boat of size $x$ as a string of characters that looks like this:

For example, a boat of size $3$ looks like this: \\\___/// (_ appears $3$ times). FlaviuS also found a string of $N$ characters, $S$, composed only of the characters \, _, and /. He has $Q$ queries of the form ($l$, $r$): What is the maximum size of a boat that is a subsequence of the subarray $S_l, S_{l+1}, \dots, S_r$?

A subsequence is obtained from another string by deleting some elements while keeping the order of the remaining elements. For example, \_ is a subsequence of the string \/_/, but _\ is not a subsequence of the string \/_/.

Input data

The first line contains two numbers, $N$ and $Q$, representing the length of the string and the number of questions FlaviuS asks. The second line contains the string $S$. The next $Q$ lines contain two numbers each, $l$ and $r$.

Output data

On line $i$, $1 \leq i \leq Q$, there will be a single number $x$, the maximum size of a boat.

Constraints and clarifications

• $1 \leq N, Q \leq 10^6$
• $1 \leq l \leq r \leq N$ for each query
• If there is no boat in the chosen subarray for a query, the output will be $0$.

Example

stdin

17 6
\_/\/_\___/_/\/_/
1 2
1 3
1 17
3 10
2 16
5 10

stdout

0
1
3
0
2
0

Explanation

For the first query, the subarray is \_, so there is no boat.

For the second query, the subarray is \_/, so there is a boat of size $1$.

For the third query, the subarray is the entire string. There is a boat of size $3$ formed by the characters at positions $1, 4, 7, 8, 9, 10, 11, 13, 17$. A boat of size $3$ looks like this: \\\___///.