동서로 무한히 길게 뻗은 UCPC 도로에 $1$의 간격으로 무한히 많은 화분을 놓아 민들레 화단을 만들었다. 모든 화분에는 정수 번호가 매겨져 있는데, $0$번 화분을 기준으로 동쪽으로 $k$만큼 떨어진 화분의 번호는 $k$번, 서쪽으로 $k$만큼 떨어진 화분의 번호는 $-k$번이다. 각 화분에는 최대 한 송이의 민들레만 자랄 수 있다.

민들레는 바람이 불면 그 방향으로 $1$만큼 떨어진 화분에 홀씨를 날린다. 심거나 바람에 날려 화분에 떨어진 민들레 씨는 그 화분에 다른 민들레가 없으면 빠르게 자라나 다음 날이면 홀씨를 날릴 수 있게 된다. 각 민들레마다 홀씨는 충분히 많아 다 떨어지는 일은 없다.

시우는 로봇을 이용해 $N$일에 걸쳐 민들레 화단을 관찰하려 한다. 로봇은 화단을 관찰하는 동안 매일 하루에 하나씩 명령을 입력받아 수행한다. 로봇이 수행할 수 있는 명령의 종류는 다음과 같다.

• L: 서쪽으로 바람을 일으킨다. 모든 정수 $x$에 대해, $x$번 화분에 민들레가 심겨 있고 $(x-1)$번 화분에 민들레가 없다면 다음 날 $(x-1)$번 화분에 새 민들레가 자란다.
• R: 동쪽으로 바람을 일으킨다. 모든 정수 $x$에 대해, $x$번 화분에 민들레가 심겨 있고 $(x+1)$번 화분에 민들레가 없다면 다음 날 $(x+1)$번 화분에 새 민들레가 자란다.
• C x: $x$번 화분에 민들레 씨를 심는다. $x$번 화분에 민들레가 없다면 다음 날 새 민들레가 자란다. ($-10^9 \le x \le 10^9$; $x$는 정수)
• Q: 현재 민들레가 있는 화분의 개수를 기록한다.

화단 관찰을 시작하기 전에는 $0$번 화분에만 민들레 한 송이가 심겨 있다. 시우가 $N$일 동안 로봇에게 요청한 명령의 목록이 주어졌을 때, 명령를 수행하는 프로그램을 작성하시오.

Input

첫 줄에 명령의 수 $N$이 주어진다. ($1 \le N \le 200\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 한 줄에 하나씩 명령이 주어진다. 그중 $i$번째 명령은 로봇이 $i$일에 처리해야 하는 명령을 의미한다. ($1 \le i \le N$)

명령 중 Q는 하나 이상 있다.

Output

명령으로 Q가 주어진 날마다, 그날 민들레가 있는 화분의 개수를 한 줄에 하나씩 시간순으로 출력한다.

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