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
.
Constraints
is a permutation of
.
There are at most queries of the third type.
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
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 .
Comments