Problem F
Tónlistarlisti

Atli is very disorganized and only has one playlist of songs to listen to. All songs he likes go into the top of the list, and when he listens to music he starts with the top song and listens to them in order. If he has listened to them all, he starts anew from the top.

For some reason the program he uses to listen to music cannot show him how often he has listened to each song. Thus he asks you to make a program that can maintain such statistics. He only counts times when he listens to a song from start to end without interruption.

Input

The first line in the input contains one integer $q$, the number of queries.

Next there are $q$ lines, each with one query. They start with a single letter that denotes the type of query. If the line starts with a $P$, a positive integer $\le {10}^9$ follows, the number of seconds Atli listened to music for. Atli always starts at the top of the list and pauses when the time is up. If the line starts with an $L$, a string with a song name follows, and then the length of that song in seconds. This means Atli added this song to the top of his playlist, or deleted it from the playlist if it was already present. If the line starts with $Q$ a song name will follow and the program should print how often Atli has listened to that song. The song names only contain lower case English letters and underscores. The total length of all song names in the input is at most $2\cdot {10}^6$. The playlist is empty at the start and Atli will never listen to music while the playlist is empty. No two different songs have the same name.

Output

For each query that starts with a $Q$, print how often Atli has listened to the corresponding song.

Scoring

3
L roundabout 509
P 7200
Q roundabout

14

8
L uufo 239
L ghoul 271
L ghost 349
P 858
P 619
P 9139
L mystery_circles_ultra 239
Q ghoul

11

13
Q nymphis_fae
L spider_dance 106
L crab_rave 256
P 824
L alchemy 300
L crab_rave 256
P 1000
Q crab_rave
L infestation 274
L sea_shanty_two 128
L crab_rave 256
P 1577
Q crab_rave

0
2
4