.ZIP

# Balls Solution

Objective

The objective of this problem is to test the students’ understanding on Doubly Linked List.

Problem Description

There are N balls labelled with 1, 2, 3,…, N, from left to right. Now, we want to do two kinds of operations:

1. “A x y”: move the ball labelled x to the left of the ball labelled y, where x ≠ y.

Reminder: if x is on the left of y, you may ignore this operation.

2. “B x y”: move the ball labelled x to the right of the ball labelled y, where x ≠ y.

Reminder: if x is on the right of y, you may ignore this operation.

3. “R x”: remove the ball labelled x.

Print the final arrangement after M operations.

Input

The first line contains two integers, N (1<= N <= 1,000) and M (1<= M <= 1,000). The next M lines contain the operations.

Output

Output the final arrangement of the N balls from left to right. Each number is followed by a whitespace.

Sample Input

10 5

A 2 1

A 10 1

A 5 6

B 6 9

R 3

Sample Output

2 10 1 4 5 7 8 9 6

Explanation

0th operation: 1 2 3 4 5 6 7 8 9 10

1st operation: 2 1 3 4 5 6 7 8 9 10

2nd operation: 2 10 1 3 4 5 6 7 8 9

3rd operation: 2 10 1 3 4 5 6 7 8 9

4th operation: 2 10 1 3 4 5 7 8 9 6

5th operation: 2 10 1 4 5 7 8 9 6

Algorithm Template

1. What data structure should be used to simulate the operations?

2. What should be updated for insertion and deletion operations?

3. What is the complexity for your algorithm?

You'll get a 94.9KB .ZIP file.