키파는 버거운 직장에서 벗어나 새로운 직업에 도전하고자 햄버거집을 차렸다. 키파는 케이크를 여러 차례 만들면서 빵은 좀 구워 봤지만 햄버거를 만드는 것은 처음이었기 때문에, 위아래의 구분이 있는 빵을 적당히 구워서 햄버거 패티로 햄버거가 들어간 탄수화물 폭탄의 버거운 버거를 만들어 팔기로 했다.</p>

버거운 버거의 예시.

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

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

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

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

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

입력 형식

첫 줄에 양의 정수 N이 주어진다.</p>

둘째 줄에 길이가 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)마다 버거운 버거의 높이를 한 줄에 하나씩 출력한다.

예제 입력

4
(()(
5
1 2 3
2 1 4
1 1 4
1 2 2
2 3 4

예제 출력

6
4