After FlaviuS mysteriously discovered that he is ambidextrous, he defined a boat of size as a string of characters that looks like this:
For example, a boat of size looks like this: \\\___///
(_
appears times). FlaviuS also found a string of characters, , composed only of the characters \
, _
, and /
. He has queries of the form (, ): What is the maximum size of a boat that is a subsequence of the subarray ?
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, and , representing the length of the string and the number of questions FlaviuS asks. The second line contains the string . The next lines contain two numbers each, and .
Output data
On line , , there will be a single number , the maximum size of a boat.
Constraints and clarifications
- for each query
- If there is no boat in the chosen subarray for a query, the output will be .
# | Points | Constraints |
---|---|---|
0 | 0 | Example |
1 | 9 | |
2 | 22 | |
3 | 33 | |
4 | 36 | No further constraints |
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 .
For the third query, the subarray is the entire string. There is a boat of size formed by the characters at positions . A boat of size looks like this: \\\___///
.