Dynamic Parentheses String Operations

You are given a parentheses string \(S\) which initially is (). Then, you are given \(n\) operations. Each operation is one of the following three types:

• Type 1: Append a pair of parentheses to the end of \(S\) (i.e. if \(S\) was originally, then it becomes \(S()\)).
• Type 2: Add a pair of parentheses around \(S\) (i.e. \(S\) becomes \((S)\)).
• Type 3: Cancel the \(x\)th operation, i.e. completely remove all the effects caused by the \(x\)th operation. Note that if the \(x\)th operation is itself a cancellation which canceled the \(y\)th operation, then canceling it will restore the effect of the \(y\)th operation.

After each operation, print the number of non-empty contiguous substrings of \(S\) that form a valid parentheses sequence. A parentheses string is valid if and only if the number of left and right parentheses are equal and in every prefix the number of left parentheses is no less than the number of right parentheses.

inputFormat

The first line contains an integer \(n\) (the number of operations). The following \(n\) lines each represent an operation.

An operation is given in one of the two formats:

• For type 1 and type 2 operations, the line contains a single integer: either 1 or 2.
• For a type 3 operation, the line contains two integers: 3 x, indicating that the \(x\)th operation is to be canceled. It is guaranteed that \(x\) is less than the current operation number.

outputFormat

Output \(n\) lines. In the \(i\)th line, print the number of valid non-empty contiguous substrings of \(S\) after performing the first \(i\) operations.

sample

3
1
2
1

3
1
3

</p>