Qarentheziz 수열

Ryan은 (와 )로만 이루어진 문자열에 관심이 많다. 특히 균형 잡힌 문자열을 좋아한다. 균형 잡힌 문자열은 다음 규칙으로 만들 수 있다.

• ()는 균형 잡힌 문자열이다.
• 균형 잡힌 문자열 두 개를 이어 붙인 문자열은 균형 잡힌 문자열이다.
• $T$가 균형 잡힌 문자열이면, (, $T$, )를 이 순서대로 이어 붙인 문자열은 균형 잡힌 문자열이다.

예를 들어 ()()와 (()())는 균형 잡힌 문자열이다. )(, )()((), (는 균형 잡힌 문자열이 아니다.

Ryan은 문자열 $T$의 슬픔을 $T$를 균형 잡힌 문자열로 만드는 데 필요한 연산의 최소 횟수로 정의한다. 연산은 임의의 순서로, 임의의 횟수만큼 사용할 수 있다.

• $T$의 맨 앞에 )를 추가한다.
• $T$의 맨 뒤에 (를 추가한다.
• $T$의 인접한 두 문자를 서로 바꾼다.

Ryan은 (와 )로만 이루어진 길이 $N$의 문자열 $S$를 갖고 있다. $Q$개의 질의를 주어진 순서대로 처리한다. 질의는 두 종류이다.

• 1 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지(양 끝 포함) 각 문자를 확인해서, (는 )로, )는 (로 바꾼다.
• 2 l r: $S$의 $l$번째 문자부터 $r$번째 문자까지 부분 문자열의 슬픔을 출력한다.

첫 줄에 두 정수 $N$과 $Q$($2 \le N \le 150\,000$, $1 \le Q \le 150\,000$)가 공백으로 구분되어 주어진다. 둘째 줄에는 (와 )로만 이루어진 길이 $N$의 문자열 $S$가 주어진다. 이후 $Q$개의 줄에는 각각 세 정수 $t_i$, $l_i$, $r_i$($1 \le t_i \le 2$, $1 \le l_i \le r_i \le N$)가 공백으로 구분되어 주어진다. $t_i = 2$인 질의가 적어도 하나 있다.

$t_i = 2$인 각 질의에 대해, $l_i$번째 문자부터 $r_i$번째 문자까지 부분 문자열의 슬픔을 한 줄에 하나씩 출력한다.