시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 228 0 0 0.000%

문제

치삼이는 오늘도 노래를 듣는다.

치삼이는 새로운 노래를 발견하면 즉시 재생버튼을 누른다. 새로운 노래를 재생 버튼을 눌러 추가할 경우, 그 노래는 기존 플레이리스트의 최상단에 추가된다. 새로운 노래가 추가된 후 L을 눌러 노래를 들으면 그 노래부터 재생된다. 치삼이는 랜덤재생을 하지 않으므로, 플레이리스트에 추가된 순서대로 노래를 듣는다. 치삼이는 반복재생 설정을 하지 않았기 때문에 전체 노래 재생이 끝나면 더 이상 노래를 듣지 않는다. 노래를 듣던 치삼이는 자신이 어떠한 기준에 따라 노래를 질려 한다는 것을 깨달았다. 그래서 심심했던 치삼이는 자신이 노래를 질려 하는 정도를 ‘치삼지수’라 이름 붙이고 자신의 ‘치삼지수’를 식으로 나타냈다.

치삼지수 = 해당 곡의 위치(플레이리스트 상단부터 1, 2, 3, …, N) × 들은 시간

(이 때, 해당 곡의 위치는 치삼이가 곡을 들을 당시의 플레이리스트로 계산한다.)

치삼이는 치삼지수가 일정 수치 S 이상이 되면 자동으로 플레이리스트에서 제거하고 제거한 노래의 제목을 출력하는 프로그램을 만들고자 한다. 프로그램은 추가로 다음의 6가지 동작을 수행할 수 있다.

AR 플레이리스트에 있는 곡 중에서 가장 질린 곡을 리스트에서 제거하고 제거한 곡의 제목을 출력한다. (가장 질린 곡이 여러 개일 경우 플레이리스트 가장 상단에 위치한 한 개의 곡을 제거한다.)
R 문자열 지정한 곡을 리스트에서 제거하고 해당 곡의 치삼지수를 출력한다.
P 문자열 정수 곡을 새로 발견해 재생버튼을 누른다. (곡의 제목과 길이가 주어진다.)
AE 현재 플레이리스트에서 치삼이가 가장 질려 하는 곡의 치삼지수를 출력한다. (여러 개가 존재할 경우 플레이리스트 가장 상단에 위치한 한 개의 곡을 출력한다.)
E 문자열 지정 곡의 치삼지수를 출력한다.
L T 지정 시간만큼 곡을 듣는다. (T ≤ 100,000,000)

하지만 치삼이는 프로그램을 만드는데 어려움을 겪고 있다. 여러분이 치삼이를 도와 프로그램을 완성시킬 수 있도록 도와주자.

입력

첫번째 줄에 세 개의 정수로 현재 플레이리스트 곡 수 N(1 ≤ N ≤ 10,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 10 5
pizza 3
papercut 5
joshua 2
L 2
L 3
P blue 4
E blue
E papercut
L 30
AE
R joshua
AR
AR

예제 출력 1

0
4
pizza
papercut
4
4
blue
-1