북극여우는 괄호를 뒤집어

극지 연구소에서 연구하는 협이는 저번에 북극곰이 괄호를 찢는다는 특성을 알아낸 뒤로 괄호로 여러 실험을 하고 있었다. 잠시 쉬고 돌아온 협이는 실험 중이던 괄호가 바뀐 것을 알아챘다. 범인을 찾으려고 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 \le N = |S| \le 1\,000\,000$, $1 \le Q \le 20\,000$)

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

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

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

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