29162번 - 북극여우는 괄호를 뒤집어

문제

극지 연구소에서 연구 중인 협이는 저번에 북극곰이 괄호를 찢는다는 특성을 알아낸 후 괄호로 여러가지 실험을 하고 있었다. 연구를 하다가 잠깐 쉬고 온 협이는 실험 중이던 괄호가 바뀐 것을 알아차렸다. 범인을 찾기 위해 CCTV를 찾아본 결과 북극여우가 괄호들을 뒤집었다는 사실을 알아냈다. 북극에 사는 동물의 새로운 특성에 신이 난 협이는 북극여우가 어떤 습성을 가지고 있는지 관찰하려 한다. 올바른 괄호 쌍의 개수와 북극여우와 관계가 있을 것이라 생각한 협이는 관찰 결과를 통해 올바른 괄호 쌍이 몇 개 있는지 세어보려 한다.

올바른 괄호 쌍의 개수는 연속된 “()”인 쌍 하나를 지우고 남은 문자열을 붙이는 연산을 재귀적으로 진행했을 때, “()”인 쌍을 최대로 제거하는 횟수가 올바른 괄호쌍의 개수이다.

문자열 $S$가 주어질 때, 북극여우는 다음 3ドル$가지 행동을 할 수 있다. $l,ドル $r$이 주어졌을 때, $l \le i \le r$인 $i$에 대해서

• 1ドル$ $l$ $r$: 모든 $i$에 대해 $s_i$가 ‘(’ 이면 ‘)’으로, ‘)’이면 ‘(’ 로 바꾼다.
• 2ドル$ $l$ $r$: 모든 $i$에 대해 문자 $s_i$의 위치를 $s_{r+l-i}$으로 옮긴다.
• 3ドル$ $l$ $r$: 부분 문자열 $s_l, s_{l + 1}, \cdots, s_r$을 180ドル$도만큼 회전시킨다.

그리고 협이는 북극여우가 행동하는 중에, 임의의 구간 $[l,r]$에 대하여 올바른 괄호 쌍의 개수를 질문할 수 있다.

• 4ドル$ $l$ $r$: 부분 문자열 $s_l, s_{l + 1}, \cdots, s_r$에서 올바른 괄호 쌍의 개수를 알려준다.

위 네 개의 질의를 순서대로 처리하며 올바른 괄호 쌍의 개수가 몇 개인지 알려주자.

입력

첫 줄에 괄호 문자열 $S$의 길이 $N$과 질의의 개수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N= \lvert S \rvert \leq 1,000円,000円;$ 1ドル \leq Q \leq 20,000円)$

둘째 줄에 길이가 $N$이고 ‘(’ 또는 ‘)’로 이루어진 공백 없는 문자열 $S$가 주어진다.

셋째 줄부터 $Q$개의 줄에 걸쳐 질의의 정보 $t,ドル $l,ドル $r$가 공백으로 구분되어 주어진다. $(1 \leq t \leq 4;$ 1ドル \leq l \leq r \leq N)$

4ドル$번 질의는 하나 이상 주어지며, 입력으로 주어지는 수는 모두 정수이다.

출력

4ドル$번 질의에 대한 답을 한 줄에 하나씩 순서대로 출력한다.

제한

힌트