시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB449930.000%

문제

노래 듣기에 진심인 편인 치삼이는 하나의 플레이리스트로 소중한 노래들을 관리하려고 한다. 치삼이가 직접 구현한 플레이리스트에는 노래마다 "치삼 지수"라는 특별한 값이 존재한다. 이 값은 아래와 같이 정의된다.

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

또한 플레이리스트에는 다음과 같은 6가지 명령이 존재한다.

L [정수 T]

다음과 같은 규칙을 통해 지정 시간 만큼 곡을 듣는다. (1 ≤ T ≤ 100,000,000)

  • 리스트에 존재하는 노래들은 순서에 맞게 차례대로 재생된다. 
  • 만약 새로 추가된 노래가 있다면, 최근에 추가된 노래의 시작부터 듣는다.
  • 추가된 노래가 없다면, 직전에 들었던 부분이 재생된다. 예를 들어, 노래를 4초 동안 듣고 L의 수행이 멈추었을 경우 다음 L을 수행할 때 그 노래의 멈춘 순간부터 재생된다. 
  • 만약 추가된 노래가 없는데 직전에 들었던 노래가 삭제된 경우라면, 플레이리스트상에서 직전에 들었던 노래의 다음으로 존재하는 노래가 재생된다. 예를 들어 듣고 있던 노래가 아직 1초 이상 남았더라도 해당하는 노래가 삭제됐다면, 다음 L을 수행할 때에는 다음 노래의 처음부터 재생된다.
  • 더 이상 재생할 노래가 없거나 조건을 만족하는 노래가 없다면 재생을 정지한다(반복 재생이 아니기 때문에 플레이리스트가 끝나면 재생이 끝난다.).
  • 각 노래마다 재생이 완료된 시점(다음 노래로 넘어가거나 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번째 줄부터 개의 명령이 주어진다. 명령은 위에서 언급한 6가지이다.

출력

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

예제 입력 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

예제 출력 1

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