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:
- Add a swap to the beginning of the list.
- Add a swap to the end of the list.
- 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 .
is a permutation of .
There are at most queries of the third type.
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
The first line contains integers and .
Then queries follow, each given on a single line. The first character on each line is either
Q. If it is
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 .
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 .
4 5 B 3 4 E 2 3 Q 2 4 1 3 E 2 3 Q 3 1 2 4
2 1 3 4 3 1 4 2
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 .