Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

G. Queue Mischief
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The grand final of the Tengo-lengo-tengo World Cup is about to begin! The decisive match will be played between Altos and Bahia, and the line to enter the stadium is pure chaos.

The line is made entirely of fans of the two teams. As tradition dictates, whenever an Altos fan is standing before (closer to the stadium entrance than) a Bahia fan, we say there is a banter happening between them.

Mathematically, if we view the line as a string $$$S$$$ made of the letters 'A' and 'B', a banter is formed by each pair of indices $$$(i, j)$$$ such that $$$i \lt j$$$, where $$$S[i]$$$ is an Altos fan ('A') and $$$S[j]$$$ is a Bahia fan ('B').

The stadium organization recorded $$$Q$$$ events in the line, which can be of $$$4$$$ types:

  • Type 1: A fan of team $$$X$$$ ('A' or 'B') joins the end of the line.
  • Type 2: A mischievous fan of team $$$X$$$ ('A' or 'B') cuts in at the exact front of the line.
  • Type 3: The fan at the end of the line gets tired of waiting and leaves.
  • Type 4: The fan at the front of the line goes through the turnstile and enters the stadium.

Your task is to compute the total number of banters happening in the line immediately after each event.

Input

The first line of the input contains an integer $$$Q$$$ ($$$1 \leq Q \leq 10^{6}$$$), representing the number of events.

The next $$$Q$$$ lines describe the events. Each line starts with an integer $$$T$$$ ($$$1 \leq T \leq 4$$$):

  • If $$$T = 1$$$, it is followed by a character $$$X$$$ ('A' or 'B'), indicating the team of the fan who joined the end of the line.
  • If $$$T = 2$$$, it is followed by a character $$$X$$$ ('A' or 'B'), indicating the team of the fan who joined the front of the line.
  • If $$$T = 3$$$, the fan at the end of the line leaves (no character is given).
  • If $$$T = 4$$$, the fan at the front of the line enters the stadium (no character is given).

It is guaranteed that operations of type $$$3$$$ and $$$4$$$ are never called when the line is empty.

Output

For each query, print a single integer on one line: the number of banters happening in the line at the current moment.

Examples
Input
1
2 A
Output
0
Input
5
1 A
1 B
1 B
1 A
1 B
Output
0
1
2
2
4
Input
5
1 A
2 B
2 A
3
4
Output
0
0
1
1
0
Note

Explanation for example 2

In the second example, after each event the line becomes, respectively, A, AB, ABB, ABBA, and ABBAB. The numbers of banters in these lines are $$$0$$$, $$$1$$$, $$$2$$$, $$$2$$$, and $$$4$$$, because each banter corresponds to an A that appears before a B.

Explanation for example 3

In the third example, after each event the line becomes, respectively, A, BA, ABA, AB, and B. Thus, the numbers of banters are $$$0$$$, $$$0$$$, $$$1$$$, $$$1$$$, and $$$0$$$.