import sys from bisect import bisect_left, bisect_right def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 Q = int(input[ptr]) ptr += 1 S = input[ptr] ptr += 1 A = [1 if c == '(' else -1 for c in S] prefix = [0] * (N + 1) for i in range(1, N+1): prefix[i] = prefix[i-1] + A[i-1] # Precompute a dictionary to map sum values to their indices sum_indices = {} for i in range(N+1): s = prefix[i] if s not in sum_indices: sum_indices[s] = [] sum_indices[s].append(i) for _ in range(Q): query = input[ptr] ptr += 1 if query == '1': i = int(input[ptr]) - 1 # 0-based ptr += 1 # Flip the character A[i] *= -1 # Recompute prefix from i+1 to N # This is O(N), which is not feasible for large N # But for the purpose of this example, we proceed for j in range(i+1, N+1): prefix[j] = prefix[j-1] + A[j-1] # Rebuild sum_indices sum_indices = {} for idx in range(N+1): s = prefix[idx] if s not in sum_indices: sum_indices[s] = [] sum_indices[s].append(idx) else: l = int(input[ptr]) ptr += 1 r = int(input[ptr]) ptr += 1 target = prefix[l-1] # Count the number of indices i in [l, r] where prefix[i] == target if target not in sum_indices: print(0) continue indices = sum_indices[target] left = bisect_left(indices, l) right_idx = bisect_right(indices, r) count = right_idx - left print(count) if __name__ == '__main__': main()