치삼이의 플레이리스트

시간 제한1초메모리 제한1024 MB

요약

재생 중인 노래는 초마다 순번만큼 점수가 쌓이고, 점수가 S 이상이면 목록에서 제거됩니다. 이 과정을 시뮬레이션하고 최댓값 제거, 삭제, 조회 명령을 처리합니다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 해시맵, 힙, 연결 리스트
정답자: 아직 제출이 없습니다

문제

노래 듣기를 좋아하는 치삼이는 하나의 플레이리스트로 소중한 노래들을 관리하려고 한다. 치삼이가 직접 구현한 플레이리스트에서는 노래마다 "치삼 지수"라는 값이 있다. 이 값은 다음과 같이 정의된다.

모든 노래는 치삼 지수를 가지며, 초깃값은 0이다.
노래를 1초 들을 때마다, 그 노래의 치삼 지수는 플레이리스트에서의 번호만큼 증가한다. 예를 들어 노래가 플레이리스트의 10번째라면 1초 들을 때마다 치삼 지수가 10씩 누적된다. 번호는 플레이리스트 최상단을 1로 하여 아래로 갈수록 1씩 커진다.
노래 재생이 끝난 시점(노래가 끝나거나 재생 시간이 다 된 시점)에 누적된 치삼 지수가 S 이상이면, 그 노래를 플레이리스트에서 자동으로 제거한다.

플레이리스트에는 다음 6가지 명령이 있다.


L [정수 T]	다음 규칙에 따라 지정한 시간 T만큼 노래를 듣는다. (1 ≤ T ≤ 100,000,000)* 리스트에 있는 노래는 순서대로 재생된다.* 새로 추가된 노래가 있으면, 가장 최근에 추가된 노래의 처음부터 듣는다.* 추가된 노래가 없으면, 직전에 듣던 부분부터 재생한다. 예를 들어 노래를 4초 듣다가 L 명령이 멈췄다면, 다음 L 명령은 그 노래가 멈춘 순간부터 재생한다.* 직전에 듣던 노래가 삭제되었다면, 플레이리스트에서 그 노래 바로 다음에 있는 노래가 처음부터 재생된다. 삭제된 노래에 1초 이상 남아 있었더라도 마찬가지다.* 재생할 노래가 없거나 조건을 만족하는 노래가 없으면 재생을 멈춘다. 반복 재생은 하지 않으므로 플레이리스트가 끝나면 재생도 끝난다.* 각 노래의 재생이 끝난 시점(다음 노래로 넘어가거나 T만큼 재생된 시점)마다 치삼 지수를 확인해 제거 여부를 정한다. 제거한 뒤에는 제목을 한 줄에 하나씩 출력한다.
AR	플레이리스트에 있는 곡 중 치삼 지수가 가장 높은 곡을 리스트에서 제거하고, 제거한 곡의 제목을 출력한다. 그런 곡이 여러 개라면 최상단의 곡을 제거한다. 플레이리스트가 비어 있으면 -1을 출력한다.
R [문자열]	제목이 문자열과 일치하는 곡을 플레이리스트에서 제거하고, 그 곡의 치삼 지수를 출력한다. 그런 곡이 없으면 -1을 출력한다.
P [문자열] [정수]	새로 발견한 곡을 플레이리스트의 최상단에 추가한다. 주어지는 문자열과 정수는 곡의 제목과 길이다. 플레이리스트에 있었던 곡의 제목은 다시 주어지지 않는다.
AE	플레이리스트에 있는 곡들의 치삼 지수 최댓값을 출력한다. 플레이리스트가 비어 있으면 -1을 출력한다.
E [문자열]	제목이 문자열과 일치하는 곡이 플레이리스트에 있으면 그 곡의 치삼 지수를 출력한다. 그런 곡이 없으면 -1을 출력한다.

입력

첫 번째 줄에 세 정수가 주어진다. 현재 플레이리스트의 곡 수 N(1 ≤ N ≤ 1,000), 주어지는 명령의 개수 M(1 ≤ M ≤ 10,000), 곡이 삭제되는 기준 S(1 ≤ S ≤ 100,000,000)이다.

두 번째 줄부터 N+1번째 줄까지 현재 플레이리스트가 위에서부터 차례로 주어진다. 각 줄에는 곡의 제목 Ai와 곡의 길이를 나타내는 양의 정수 Ti(1 ≤ Ti ≤ 1,000)가 주어진다.

곡의 제목은 중복되지 않으며, 알파벳 소문자로만 이루어져 있고 50글자를 넘지 않는다. N+2번째 줄부터 M개의 명령이 주어진다. 명령은 위에서 설명한 6가지이다.

출력

명령에서 출력을 요구하는 문장을 한 줄에 하나씩 출력한다.

예제1

예제 1

입력

3 17 5
pizza 3
papercut 5
joshua 2
L 2
E pizza
L 2
E pizza
P blue 4
E blue
E papercut
L 8
E papercut
L 30
AE
L 30
E blue
E pizza
R joshua
AR
AR

예상 출력

2
3
0
2
pizza
4
papercut
4
4
-1
4
blue
-1