음악 목록

Atli는 매우 정리 정돈을 못해서 들을 노래 재생 목록을 하나만 가지고 있다. 그가 좋아하는 모든 노래는 목록의 맨 위에 들어가며, 음악을 들을 때는 맨 위의 노래부터 시작해 순서대로 듣는다. 모든 노래를 다 들었다면 맨 위부터 새로 시작한다.

어떤 이유에서인지 Atli가 음악을 듣는 데 사용하는 프로그램은 그가 각 노래를 몇 번 들었는지 보여 줄 수 없다. 따라서 그는 이러한 통계를 관리할 수 있는 프로그램을 만들어 달라고 요청한다. 그는 노래를 처음부터 끝까지 중단 없이 들은 경우만 횟수에 포함한다.

채점

그룹 | 점수 | 제한 조건

1 | 20 | $1 \leq q \leq 1\,000$, 노래는 재생 목록에서 절대 제거되지 않으며, 각 노래의 길이는 $1$이다

2 | 20 | $1 \leq q \leq 1\,000$, 노래는 재생 목록에서 절대 제거되지 않는다

3 | 30 | $1 \leq q \leq 5 \cdot 10^5$, 노래는 재생 목록에서 절대 제거되지 않는다

4 | 30 | $1 \leq q \leq 5 \cdot 10^5$

입력의 첫 번째 줄에는 질의의 수를 나타내는 정수 하나 $q$이 주어진다.

다음 $q$개의 줄에는 각각 질의 하나가 주어진다. 각 줄은 질의의 종류를 나타내는 문자 하나로 시작한다. 줄이 $P$로 시작하면 Atli가 음악을 들은 시간(초)을 나타내는 양의 정수 $\leq 10^9$이 뒤따른다. Atli는 항상 목록의 맨 위부터 시작하며 시간이 다 되면 일시 정지한다. 줄이 $L$로 시작하면 노래 이름을 나타내는 문자열과 그 노래의 길이(초)가 뒤따른다. 이는 Atli가 이 노래를 자신의 재생 목록 맨 위에 추가했음을 의미하며, 이미 재생 목록에 있다면 재생 목록에서 삭제했음을 의미한다. 줄이 $Q$로 시작하면 노래 이름이 뒤따르며, 프로그램은 Atli가 그 노래를 몇 번 들었는지 출력해야 한다. 노래 이름에는 영어 소문자와 밑줄만 포함된다. 입력에 있는 모든 노래 이름의 길이의 합은 최대 $2 \cdot 10^6$이다. 처음에 재생 목록은 비어 있으며, Atli는 재생 목록이 비어 있을 때 절대 음악을 듣지 않는다. 서로 다른 두 노래가 같은 이름을 갖는 경우는 없다.

$Q$로 시작하는 각 질의에 대해 Atli가 해당 노래를 몇 번 들었는지 출력한다.