Description

 

After graduating from NTHU CS, since your teamates and you all love singing, you are asked to write a song ordering system for them. 

Beside the basic operations: order, play, show, since someone may suddenly want to sing a certain song, so you have to add an operation called "insert". The rule of "insert" is that when you insert a new song (a totally new one or one has been ordered), it will be added to the end of all the inserted songs. And if you insert it the second or more time, it will become the next song to play (the first of all the inserted songs).

The playlist of the songs can be seen as three parts: songs have been played, songs have been inserted, and songs ordered by ordinary way. Let's denote them as played part, inserted part, ordered part, and the whole list is called playlist.

There are 4 operations in the ordering system:

• order(int k): add song k to the end of the ordered part, it's guaranteed that k is not in the playlist before.
• insert(int k): (it's guarantee that k has not been played before)
  • For song k that has been inserted at lease once(insert k): put k at the beginning of the inserted part.
  • If song k isn't in the playlist: add k to the end of the inserted part.
  • If song k is in the ordered part: move k from the ordered part to the end of the inserted part.
• play(): print the number of the next song, and move it to the played part. If there are no unplayed songs(inserted part and ordered part are both empty), please print "All songs are played.".
• show(); print the whole playlist, songs that were played in the first line, songs that are still waiting should be printed on in the second line.

 

Take the first sample testcase for example, after each operation, the playlist may be like (played part | inserted part | ordered part):

order 6:  | | 6

play: 6 | |        

order 4: 6 | | 4

insert 3: 6 | 3 | 4

show: 6 | 3 | 4

order 2: 6 | 3 | 4 2

insert 5: 6 | 3 5 | 4 2

insert 1: 6 | 3 5 1 | 4 2

show: 6 | 3 5 1 | 4 2

insert 1: 6 | 1 3 5 | 4 2

show: 6 | 1 3 5 | 4 2

 

This problem is partial judge (Don't forget to include "function.h"!), you need to finish the following functions:

• void initialize(): you can do whatever you want to initialize the class, it's also ok to do nothing
• void order(int k): same as the above
• void play(): same as the above
• void show(): same as the above
• void insert(int k): same as the above
• void destroy(): same as initialize, but this is used to destroy the class

The function print(song *st, song *en) can print songs in [st, en), you can use it to avoid presentation error.

 

Input

The first line contains an integer T -- the testcases.

In the first line of each testcase is an integer N -- the number of operations.

The following N lines will be the operations -- order k, insert k, play, show.

For testcase 1~3: 1 <= N <= 1000.

For testcase 4~6: 1 <= N <= 1e5. It's guarantee that the number of "show" is under 200.

For all testcases: 1 <= T <= 10, 1 <= k <= 1e6.

Output

For operation "play", print the number of the next song to play, if there are no such song, please print "All songs are played.".

For operation "show", print two lines, the first line contains all the number of played songs, while the second line contains the songs have been ordered or inserted but haven't been played yet.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13861.cpp

Partial Judge Header

13861.h

Tags

Discuss