Starting with an empty sequence S, we have set of N queries.
There are 5 types of queries:
1. PF x : Push integer x to front of sequence S
2. PB x : Push integer x to back of sequence S
3. RF : Remove element at the front of sequence S
4. RB : Remove element at the back of sequence S
5. RA y : Print the element currently at rank y in sequence S.

Ranks start from 1, 2, .. upto length of S. The element at the front has rank 1 and element at the back has rank equal to length of S.

After all the N queries are processed, you should print the sequence S in sorted order. 

It is guaranteed that, when sequence S is empty none of the queries of type 3, 4, or 5 will occur.

Input

First line contains integer N, denoting the number of queries
Each of the next N lines, contains a single query of one of the 5 types described above.

Output

For each query of type 5, print the integer at the given rank.
After processing all the queries, print the sorted sequence S. Elements of S should be separated by a space.

Constraints

1 <= N <= 10000
1 <= x <= 10^9
1 <= y <= length(S) <= 10000

Example

Input:
7
PF 1
PB 4
PF 3
RA 1
RA 2
RF
PB 5

Output:
3
1
1 4 5