You have a list of swaps, initially empty. Each swap is a pair of integers ~(x, y)~, representing indices in an array of length ~N~. Process ~Q~ of the following operations:
- Add a swap ~(x, y)~ to the beginning of the list.
- Add a swap ~(x, y)~ to the end of the list.
- Output a permutation of the first ~N~ 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 ~P~.
A swap ~(x, y)~ is applied by swapping the numbers at indices ~x~ and ~y~.
~2 \le N \le 300~
~1 \le Q \le 3 \times 10^6~
~1 \le x < y \le N~
~P_1, P_2, \dots, P_N~ is a permutation of ~1, 2, \dots, N~.
There are at most ~3000~ queries of the third type.
Subtask 1 [50%]
~1 \le Q \le 3 \times 10^3~
Subtask 2 [50%]
No additional constraints.
The first line contains ~2~ integers ~N~ and ~Q~.
Then ~Q~ queries follow, each given on a single line. The first character on each line is either
Q. If it is
E, then two integers ~x~ and ~y~ 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 ~N~ integers follow, representing the target permutation ~P~.
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 ~P~.
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 ~[(3, 4), (2, 3)]~, we obtain
2 4 1 3.
In the second query, our swap list is ~[(3, 4), (2, 3), (2, 3)]~.