Bracket Moves in Vim

Hyeonmin was asked to find a bug in a program. The client handed over the source code and a development laptop, and Hyeonmin was startled.

The first surprise was the code itself. It is a single line made only of the characters (, ), and .. Remove every . and the remaining string is a valid bracket string.

• The empty string is a valid bracket string.
• If S is a valid bracket string, then (S) is also valid. Here ( and ) are said to match each other.
• If S and T are valid bracket strings, then S**T is also valid.

The second surprise was the text editor. The laptop has only Vim installed. Vim is known for many shortcuts, but Hyeonmin knows only three.

• h: moves the cursor one character to the left. If the cursor is already at the leftmost position of the line, it does not move.
• l: moves the cursor one character to the right. If the cursor is already at the rightmost position of the line, it does not move.
• %: if the cursor is on a bracket, moves it to the matching bracket. If the cursor is not on a bracket, it does not move. The code is a valid bracket string, so a bracket without a match never needs to be considered. Typing % requires Shift + 5, so it counts as two key presses.

Debugging requires moving the cursor a great deal, so unless Hyeonmin presses keys as efficiently as possible, his fingers will not survive. For each query giving a starting position and a target position, find the minimum number of key presses needed to move the cursor from the start to the target.

The first line contains two integers $N$ and $Q$ ($1 \le N, Q \le 300,000$), the length of the code and the number of queries.

The second line contains a string of $N$ characters representing the code. The string contains no whitespace and satisfies the conditions above.

Each of the next $Q$ lines contains two integers $s$ and $e$ ($1 \le s, e \le N$), separated by a single space. They are the current cursor position and the target position.

For each query, print on its own line the minimum number of key presses needed to move the cursor from the current position to the target position.