버거운 버거

키파는 버거운 직장을 그만두고 새 일을 시작하려고 햄버거집을 열었다. 케이크를 여러 번 만들면서 빵을 구워 본 적은 있지만 햄버거는 처음 만들어 봤기 때문에, 위아래 구분이 있는 빵을 알맞게 구워 햄버거 패티와 함께 탄수화물 폭탄인 버거운 버거를 만들어 팔기로 했다.

버거운 버거의 예시.

버거운 버거의 엄밀한 정의는 다음과 같다.

• 속이 위로 온 빵 X 위에 속이 아래로 온 빵 Y를 올린 것은 버거운 버거이다. 이때 X를 Y의 대응하는 쌍, Y를 X의 대응하는 쌍이라 한다.
• 속이 위로 온 빵 X 위에 버거운 버거를 올리고 그 위에 속이 아래로 온 빵 Y를 올린 것은 버거운 버거이다. 마찬가지로 이때 X를 Y의 대응하는 쌍, Y를 X의 대응하는 쌍이라 한다.
• 버거운 버거 위에 버거운 버거를 올린 것은 버거운 버거이다.
• 위 세 규칙으로 만들 수 없는 것은 버거운 버거가 아니다.

키파는 빵 굽는 기계 N개를 일렬로 세워 두고 동시에 다루고 있다. 기계 하나는 빵을 하나만 구울 수 있다. 가장 왼쪽 기계부터 오른쪽으로 1부터 번호를 붙이자. 키파가 가게를 운영하는 동안 다음 두 가지 상황 중 하나가 Q번 발생할 수 있다.

• a번 기계부터 b번 기계까지의 빵이 곧 타려고 하기 때문에 각각 뒤집어 줘야 한다.
• 손님이 a번 기계부터 b번 기계까지의 빵을 차곡차곡 쌓아 주기를 원한다. 즉, 이 과정에서 빵을 뒤집어 쌓으면 안 되고, 가장 아래에 a번 기계에서 나온 빵, 그 위에 (a+1)번 기계에서 나온 빵, 이런 식으로 가장 위에 b번 기계에서 나온 빵이 순서대로 쌓여야 한다. 키파는 기계에 빵이 없으면 재료가 다 떨어진 것처럼 보인다고 생각했기 때문에, 한 주문이 끝난 뒤에는 그 주문을 받기 이전 상태대로 빵의 위아래를 맞춰 채워 둔다.

그런데 손님이 햄버거를 만들려고 빵을 쌓았을 때 어떤 빵은 대응하는 쌍이 존재하지 않아 버거운 버거로서 실격일 수 있다. 키파는 각 손님의 주문대로 빵을 쌓은 뒤, 이 빵을 버거운 버거로 만들기 위해 쌓아 둔 빵의 순서를 유지하면서 미리 구워 둔 빵을 최소한으로 집어넣고자 한다. 키파는 손님들의 건강에 관심이 많기 때문에 각 주문마다 버거운 버거의 높이, 즉 버거운 버거에 들어간 빵의 개수를 알고자 한다. 이를 구하는 프로그램을 작성해 키파를 도와주자.

첫 줄에 양의 정수 N이 주어진다.

둘째 줄에 길이가 N이고 (와 )로만 구성된 문자열이 주어진다. 모든 1 ≤ i ≤ N에 대해 i번째 문자가 (이면 속이 위로 온 빵이 i번 기계에, )이면 속이 아래로 온 빵이 i번 기계에 들어 있다는 뜻이다.

셋째 줄에 양의 정수 Q가 주어진다.

넷째 줄부터 Q개의 줄에 세 개의 양의 정수 t, a, b로 상황이 주어진다. t는 2 이하이며, 1 ≤ a ≤ b ≤ N이다.

t = 1인 경우 a번 기계부터 b번 기계까지의 빵을 뒤집어 줘야 함을 뜻한다.

t = 2인 경우 a번 기계부터 b번 기계까지의 빵을 꺼내 버거운 버거로 만들어 달라는 주문이 들어왔음을 뜻한다.

각 주문(t = 2)마다 버거운 버거의 높이를 한 줄에 하나씩 출력한다.

• 1 ≤ N ≤ 1,000,000
• 1 ≤ Q ≤ 300,000