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:

1. Add a swap $(x,y)$ to the beginning of the list.
2. Add a swap $(x,y)$ to the end of the list.
3. 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$.

Constraints

$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.

Input Specification

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 B, E, or Q. If it is B or 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$.

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 $P$.

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 $[(3,4),(2,3)]$, we obtain 2 4 1 3.

In the second query, our swap list is $[(3,4),(2,3),(2,3)]$.