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