Description

You are to write a program that simulates a ticket counter queue.

At the start, no one is in the queue. As time goes on, customers start coming in and queues at the end, each intending to buy a specific number of tickets. The ticket counter then serves them starting from the front of the queue. When a transaction is completed, the served customer leaves the queue. Similar to the real world, selfish customers at time appears and cut the queue.

Your programs should take in a line containing an integer M on the number of subsequent input lines, and then M lines containing:

1. The customer arrival
2. The counter transaction completion events, and
3. Commands to print out the current state of the queue.

These event line and command line formats are described in more details in the following.

1. new_normal_customer N:
   There is a new customer planning to purchase N tickets. The customer queues at the end of the ticket queue.
2. new_selfish_customer N P:
   There is a new customer planning to purchase N tickets. The customer cuts the queue and inserts them at the P position (0-indice) of the queue. Other customers, starting from the one at the original P position to the end of the queue, are pushed back one spot. (It is guaranteed that the total sum of P will not exceed 2000000)
3. done_customer:
   The counter finished serving the first customer in the queue (i.e. the customer at the front of the queue).
4. print:
   Print out the current state of the queue, starting from the front of the queue. For each customer, print out the intended number of tickets they plan to purchase. The intended ticket numbers should be separated with a space and the final ticket number should end with a newline character. If no one is in the queue, an empty line should be printed.

Your program MAY include <string>, <iostream>, <cassert>, <cstdio>, and <cstdlib>. You MUST NOT include any other C++ standard library headers.

Input

A first line containing the number M, where 0 < M <= 1000000.

The remaining lines are either a command or an event.

For parameters N and P, 0 < N <= 1000000 and 0 <= P <= 1000000.

You can assume that the P position will always be already taken when a new selfish customer cuts at position P. You can also assume that there will be at least one customer when a customer is served.

Output

For each print command, output the corresponding state of queue.

(Note that the first line of sample output contains a space character, but your program should not print any space character if the current queue is empty.)

Sample Input  Download

Sample Output  Download

Discuss