Problem B
Greedy Tax Collector
Once upon a time, there was a kingdom which had an extreme poverty problem. The king seeks to mitigate this, and instructs his tax collectors to hand out coins to his poor citizens. As one of the king’s tax collectors, your task is to distribute the coins in your purse to the citizens who come before you.
Seeing as you don’t want to part with your coin, you initially planned to only deal out the least valuable coins and keep the valuable ones yourself. However, the king anticipated your cunning scheme and has instructed a guard to watch over you to make sure you don’t keep back most of the wealth for yourself. You’ll have to deal out at least some of the most valuable coins so that the guard will not suspect you.
Afraid of losing your wealth, you instruct your subordinates to mix with the crowd and get in line. When you recognize a subordinate, you’ll give him your most valuable remaining coin, and when you recognize a peasant you’ll give him your least valuable coin. Your subordinates will of course give your money back to you at the end of the day. At times when the guard appears inattentive, you may even be able to pad your purse with a coin from the peasant in line, threathening the unlucky fellow with jail unless he “pays his taxes.”
You chuckle maliciously, satisfied with your plan. All that remains now is to come up with a quick scheme of locating your most and your least valuable coins...
Input
The first line consists of two integers: $n$ ($1 \leq n \leq 75\, 000$), the number of people in line, and $k$ ($1 \leq k \leq 75\, 000$), the number of coins initially in your purse. The second line consists of $k$ integers, denoting the values of each of the coins initially in your treasury (all coins have a value between $1$ and $2\, 000\, 000$ inclusive). Then follows $n$ lines, each of which consisting of either
-
the character “P” (indicating a peasant),
-
the character “S” (indicating a subordinate), or
-
the character “C” (for “collect tax”) followed by an integer $c_ i$ ($1 \leq c_ i \leq 2\, 000\, 000$) indicating the value of the coin you collect from the unfortunate peasant’s purse.
You never run out of coins to hand out (since if you do, you would have to take your chances with the guard and “collect tax” from the next in line).
Output
For each coin you hand out, output a line containing the value of that coin. Note: The input and output for this problem can be huge. Consider using fast input and output methods.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 979927 507183 C 193246 P S C 1231480 |
193246 979927 |
