## IITKESO207PA1_2 - Sequence

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 5Output:3

1

1 4 5

Added by: | Programming Club, IITK |

Date: | 2018-01-11 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C C99 |