A dandelion garden was created by placing an infinite number of flowerpots at intervals of $1$ along the UCPC road that stretches infinitely east-west. Each flowerpot is assigned an integer number: a flowerpot $k$ units east of pot $0$ is numbered $k$, and a flowerpot $k$ units west is numbered $-k$. At most one dandelion can grow in each flowerpot.

When the wind blows, a dandelion sends its seeds to the flowerpot $1$ unit away in that direction. A dandelion seed that is planted or blown into a flowerpot will grow quickly if no other dandelion is present there, and by the next day it will be able to send its own seeds. Each dandelion has plenty of seeds, so they never run out.

Siwoo plans to observe the dandelion garden over $N$ days using a robot. Each day during the observation, the robot receives one command and executes it. The types of commands the robot can perform are as follows:

• L: Makes the wind blow westward. For every integer $x$, if a dandelion is planted in pot $x$ and there is no dandelion in pot $(x-1)$, then by the next day a new dandelion will grow in pot $(x-1)$.
• R: Makes the wind blow eastward. For every integer $x$, if a dandelion is planted in pot $x$ and there is no dandelion in pot $(x+1)$, then by the next day a new dandelion will grow in pot $(x+1)$.
• C x: Plants a dandelion seed in pot $x$. If there is no dandelion in pot $x$, then by the next day a new dandelion will grow. ($-10^9 \le x \le 10^9$; $x$ is an integer)
• Q: Records the current number of flowerpots that contain a dandelion.

Before the observation begins, only pot $0$ has one dandelion. Given the list of commands Siwoo requested the robot over $N$ days, write a program that executes the commands.

Input

The first line contains the number of commands $N$. ($1 \le N \le 200\,000$)

The next $N$ lines each contain one command. The $i$-th command is the command the robot must process on day $i$. ($1 \le i \le N$)

There is at least one Q command among the commands.

Output

For each day when a Q command is given, output the number of flowerpots that contain a dandelion on that day, one per line, in chronological order.

Examples

Input 1

13
L
C 4
L
Q
C 2
Q
R
C 7
R
Q
R
R
Q

Output 1

5
6
11
13