17366번 - %

현민이는 최근 프로그램 하나의 버그를 찾아 달라는 의뢰를 받았다. 의뢰자로부터 프로그램의 소스 코드와 개발용 노트북을 전달받은 현민이는 깜짝 놀라고 말았다.

첫 번째로 놀란 것은 코드의 생김새였다. 현민이가 받은 코드는 (, ), . 세 종류의 문자로만 이루어진 한 줄짜리 코드였다. 그리고 코드에서 . 문자를 모두 제거한 뒤의 문자열은 올바른 괄호 문자열이었다.

• 빈 문자열은 올바른 괄호 문자열이다.
• S가 올바른 괄호 문자열일 때 (S) 역시 올바른 괄호 문자열이다. 이때 (와 )를 서로 매칭된다고 한다.
• S와 T가 올바른 괄호 문자열일 때 ST 역시 올바른 괄호 문자열이다.

두 번째로 놀란 것은 노트북에 깔려 있는 텍스트 에디터였다. 이 노트북에는 Vim밖에 깔려 있지 않았다! Vim에는 다양한 단축키가 있다고 알려져 있지만, 현민이가 아는 단축키는 단 세 개뿐이다.

• h : 커서를 왼쪽으로 한 칸 움직인다. 이미 현재 줄의 가장 왼쪽에 있는 경우는 움직이지 않는다.
• l : 커서를 오른쪽으로 한 칸 움직인다. 이미 현재 줄의 가장 오른쪽에 있는 경우는 움직이지 않는다.
• % : 현재 커서 위치에 괄호 문자가 있을 때 그와 매칭되는 괄호가 있는 위치로 움직인다. 현재 위치에 괄호 문자가 없는 경우는 움직이지 않으며, 현민이가 받은 코드는 올바른 괄호 문자열이므로 어떤 괄호 문자에 대해 매칭되는 괄호가 없는 경우는 고려하지 않는다. %는 Shift + 5로 입력하므로 키를 두 번 누르는 것으로 센다.

디버깅을 하려면 커서를 아주 많이 움직여야 하므로, 최대한 효율적으로 키를 누르지 않으면 현민이의 손가락이 무사하지 못할 것이다. 현민이가 현재 커서의 위치와 목표 위치를 말해 줄 때마다 키를 최소 몇 번 눌러야 하는지 알려 주자.

첫 줄에 코드의 길이를 의미하는 정수 N과 질문의 개수를 의미하는 정수 Q(1 ≤ N, Q ≤ 300,000)가 주어진다.

두 번째 줄에 코드를 의미하는 N글자의 문자열이 주어진다. 문자열은 공백을 포함하지 않으며 문제 내용의 조건을 만족한다.

다음 Q개의 줄에 걸쳐 각 줄에 각 질문의 현재 커서의 위치와 목표 위치를 나타내는 정수 s, e(1 ≤ s, e ≤ N)가 공백 하나를 사이에 두고 주어진다.

Q개의 줄에 걸쳐 각 줄에 각 질문에 대해 커서를 목표 위치까지 옮기는 데 필요한 최소 키 누름 횟수를 출력한다.