Problem Description

Takahashi loves "bracket mastery". He enjoys inserting or deleting opening brackets ( and closing brackets ) in strings consisting solely of these characters. Each string has a value called "bracket badness", which is defined as the minimum number of characters that must be removed to make the string "perfect". A string is considered "perfect" if there are no inconsistencies in bracket pairing. Notably, an empty string is also considered "perfect".

For example, the string ()()(()) is "perfect" and has a "bracket badness" of $0$. The string ()) becomes "perfect" by removing the last bracket, so its "bracket badness" is $1$.

Takahashi received a string $S$ from a friend and will now insert or delete brackets. Occasionally, he wonders about the "bracket badness" of a part of the current string. Your task is to determine the "bracket badness" whenever Takahashi asks.

Input Format

The input is provided from standard input in the following format:

$ Q $ $ S $ $ x_1 $ $ y_1 $ $ z_1 $ $ x_2 $ $ y_2 $ $ z_2 $ : $ x_Q $ $ y_Q $ $ z_Q $

• The first line contains the number of operations (including queries) $Q\ (1\ ≦\ Q\ ≦\ 10^5)$.
• The second line contains the string $S\ (1\ ≦\ |\ S\ |\ ≦\ 10^5)$.
• The next $ Q $ lines, where the $ i $-th line contains the $ i $-th operation represented by a character $ x_i $ and numbers $y_i,\ z_i$ separated by spaces.
• When $ x_i $ is (, it indicates an operation to insert an opening bracket at the $ y_i $-th position. Here, $ z_i $ is always $ 0 $.
• When $ x_i $ is ), it indicates an operation to insert a closing bracket at the $ y_i $-th position. Here, $ z_i $ is always $ 0 $.
• When $ x_i $ is D, it indicates an operation to delete the $ y_i $-th character. Here, $ z_i $ is always $ 0 $.
• When $ x_i $ is Q, it indicates a query for the "bracket badness" of the substring from the $ y_i $-th to the $ z_i $-th position (inclusive).
• There are no inputs that attempt to delete, query, or insert at non-existent positions. All positions are 1-indexed.

Output Format

The output consists of multiple lines. For each query by Takahashi, output the answer on a new line.

Sample Input and Output

Sample Input #1

5
(()
D 1 0
( 3 0
Q 1 2
) 1 0
Q 2 4

Sample Output #1

0
1

Sample Input #2

11
(()()(()
( 1 0
( 1 0
D 4 0
Q 2 6
) 5 0
D 8 0
Q 1 9
( 3 0
) 8 0
D 10 0
Q 5 10

Sample Output #2

1
1
4

Notes/Hints

Sample Explanation 1

After the first operation, the state is (). After the second operation, the state is ()). The string queried in the third operation is (). After the fourth operation, the state is (()). The string queried in the fifth operation is ()).

Sample Explanation 2

After the first operation, the state is ((()()((). After the second operation, the state is (((()()((). After the third operation, the state is ((()()((). The string queried in the fourth operation is (()(). After the fifth operation, the state is ((())()((). After the sixth operation, the state is ((())()(). The string queried in the seventh operation is ((())()(). After the eighth operation, the state is (((())()(). After the ninth operation, the state is (((())())(). After the tenth operation, the state is (((())())). The string queried in the eleventh operation is ))())).

见题面 Input 部分

见题面 Output 部分