726 - I2P(II)2015_Lee_Mid1

#	Problem	Pass Rate (passed user / total user)
10512	Mid1_Exam Moving books
10513	Mid1_Exam Josephus composite
10514	Mid1_Exam Queue

10512 - Mid1_Exam Moving books

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB

Description

The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on the table with book b_i adjacent to book b_i+1 for all , as shown in the diagram below:

The valid commands and limited for moving books are:

Illegal commands:

A = B
A or B is not in the range (e.g. You cannot move or remove any book that does not exist)

All illegal commands should be ignored and should have no affect on the configuration of books.

Valid commands:

move A on B

Puts book A on book B.

As below:

0 1 2 3 4

>> move 1 on 3

0 2 3 1 4

move A under B

Puts book A under of book B.

As below:

0 1 2 3 4

>> move 1 under 3

0 2 1 3 4

remove A

Remove book A from the list.

As below:

0 1 2 3 4

>> remove 1

0 2 3 4

exit

Finish moving the books, print the final status.

Input

The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n <= 10000.

The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.

You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

Your output should contains one line of sequence which represents the order of books from the bottom to the top.

Each number is followed by a single space. And you are asked to add a new line character at the end

Sample Input Download

<div>
<div>5</div>
<div>move 0 on 3</div>
<div>move 2 under 0</div>
<div>move 1 on 4</div>
<div>remove 0</div>
<div>exit</div>
</div>

Sample Output Download

3 2 4 1

10513 - Mid1_Exam Josephus composite

Status | Limits Submit

	Time	Memory
Case 1	10 sec	32 MB
Case 2	10 sec	32 MB
Case 3	10 sec	32 MB
Case 4	10 sec	32 MB
Case 5	10 sec	32 MB

Description

The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Composite numbers succession (4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ...). So in order to kill the i-th person, Josephus cousin counts up to the i-th composite.

A composite number is a positive integer that has at least one positive divisor other than one or the number itself. In other words, a composite number is any integer greater than one that is not a prime number.

For example, there are 6 people in a circle, and the sequence of couting is composite number succession (4, 6, 8, 9, 10, …).

In the beginning, the step to kill m = 4. The sequence of killing people is as follows.

1, 2, 3, 4.............................(kill 4, and m is changed to 6)

5, 6, 1, 2, 3, 5.....................(kill 5, and m is changed to 8)

6, 1, 2, 3, 6, 1, 2, 3.............(kill 3, and m is changed to 9)

6, 1, 2, 6, 1, 2, 6, 1, 2.........(kill 2, and m is changed to 10)

6, 1, 6, 1, 6, 1, 6, 1, 6, 1.....(kill 1)

Then print 6 as answer.

Input

Each line with 1 integers, n. n is the number of people.Input terminated by EOF.

Testcase 1 : 1<=n<100

Testcase 2 : 100<=n<1000

Testcase 3 : 1000<=n<10000

Testcase 4 : 10000<=n<50000

Testcase 5 : 50000<=n<100000

Output

The output will consist in separate lines containing the position of the person which life will be saved.

Sample Input Download

10

Sample Output Download

6

10514 - Mid1_Exam Queue

Status | Limits Submit

	Time	Memory
Case 1	1 sec	32 MB
Case 2	1 sec	32 MB
Case 3	1 sec	32 MB
Case 4	1 sec	32 MB
Case 5	1 sec	32 MB

Description

Consider a queue of groups. Each group has a unique ID denoted by a string of uppercase alphabets. The length of an ID is less than or equal to 6 characters.

A new comer has a certain group ID and a personal name. The length of the name is less than or equal to 10. For each new comer, you first check if there exists a group of the same ID. If yes, add this new comer to the end of that group; otherwise, create a new group at the end of the queue, and add this new comer to the new group.

Input

The input contains several lines. Each line presents the group ID and the name of a new comer. The group ID and the name are separated by a space.

The string in the last line is always "END" indicating the end of the input.

Output

The output contains one line. The first string is the ID of the last group in the queue. After that you need to print the name of members in the last group, one by one according to their coming order.

Note that there is a space after every string except the last one, which is ended with a newline character.

Sample Input Download

END

Sample Output Download

<div>BIRD Nash Victoria Natalie</div>
<div> </div>