## DMOPC '21 Contest 2 P2 - Scrambling Swaps

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You have a list of swaps, initially empty. Each swap is a pair of integers , representing indices in an array of length . Process of the following operations:

1. Add a swap to the beginning of the list.
2. Add a swap to the end of the list.
3. Output a permutation of the first positive integers such that when the list of swaps is applied in order from beginning to end, the resulting array is a given target permutation .

A swap is applied by swapping the numbers at indices and .

#### Constraints

is a permutation of .

There are at most queries of the third type.

#### Input Specification

The first line contains integers and .

Then queries follow, each given on a single line. The first character on each line is either B, E, or Q. If it is B or E, then two integers and follow, representing a swap. B indicates that you should add the swap to the beginning of the list, whereas E indicates that you should add it to the end. If the first character is Q, then integers follow, representing the target permutation .

#### Output Specification

For each query of the third type, output any initial permutation on a single line such that applying the list of swaps in order yields the target permutation .

#### Sample Input

4 5
B 3 4
E 2 3
Q 2 4 1 3
E 2 3
Q 3 1 2 4

#### Sample Output

2 1 3 4
3 1 4 2

#### Explanation

Consider the first query. If we take 2 1 3 4 and apply the swaps , we obtain 2 4 1 3.

In the second query, our swap list is .