Chisam's Playlist

Time limit1sMemory limit1024 MB

Summary

Simulate playback where each song gains its playlist position per second, remove songs that reach threshold S, and answer max and lookup queries.

Level: Medium6 of 10
Topics: Simulation, Hash map, Heap, Linked list
Solved: No attempts yet

Problem

Chisam loves listening to music, so he manages the songs he cares about in one playlist. In the playlist he built himself, every song has a value called "Chisam index". It is defined as follows.

Every song has a Chisam index, which starts at 0.
Each second a song is played, its Chisam index increases by its position number in the playlist. For example, a song in position 10 gains 10 for each second it plays. Position 1 is the top of the playlist, and each position below it is 1 larger.
When playback of a song finishes (the song ends or its play time runs out), the song is removed from the playlist automatically if its accumulated Chisam index is at least S.

The playlist also supports six commands.


L [integer T]	Plays music for T seconds under the following rules. (1 ≤ T ≤ 100,000,000)* Songs in the playlist play in order.* If a song was recently added, play it from its beginning.* If no song was added, resume the part that was playing last. For example, if a song played for 4 seconds and the L command stopped, the next L command resumes that song from where it stopped.* If the song that was playing was removed, the song right after it in the playlist plays next, from its beginning, even if the removed song had more than 1 second left.* If there are no songs left to play, or no song meets the condition, playback stops. Playback does not repeat, so it ends when the playlist ends.* When playback of each song finishes (it moves on to the next song or reaches T seconds), check its Chisam index to decide whether to remove it. After removal, print the titles one per line.
AR	Removes the song with the highest Chisam index from the playlist and prints its title. If several songs tie, remove the one at the top. If the playlist is empty, print -1.
R [string]	Removes the song whose title matches the string from the playlist and prints its Chisam index. If no such song exists, print -1.
P [string] [integer]	Adds a newly discovered song to the top of the playlist. The string and the integer are the song's title and length. A title that has already been in the playlist is never given again.
AE	Prints the maximum Chisam index among the songs in the playlist. If the playlist is empty, print -1.
E [string]	If a song whose title matches the string is in the playlist, prints its Chisam index. If no such song exists, print -1.

Input

The first line contains three integers: the current number of songs N (1 ≤ N ≤ 1,000), the number of commands M (1 ≤ M ≤ 10,000), and the removal threshold S (1 ≤ S ≤ 100,000,000).

From the second line through line N+1, the current playlist is given from top to bottom, each line holding a song title Ai and a positive integer length Ti (1 ≤ Ti ≤ 1,000).

Titles are not repeated, consist only of lowercase English letters, and are at most 50 characters long. From line N+2 onward, M commands are given. The commands are the six described above.

Output

For each command that requires output, print one line.

Examples1

Example 1

Input

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

Expected output

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