It Gets Easier. You Have To Do It Every Day. That's The Hard Part But It Does Get Easier

Start

2019-08-05 04:20 UTC

It Gets Easier. You Have To Do It Every Day. That's The Hard Part But It Does Get Easier

End

2019-08-12 04:20 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -44 days 21:36:38

Time elapsed

168:00:00

Time remaining

0:00:00

Problem O
Teque

You have probably heard about the deque (double-ended queue) data structure, which allows for efficient pushing and popping of elements from both the front and back of the queue. Depending on the implementation, it also allows for efficient random access to any index element of the queue as well. Now, we want you to bring this data structure up to the next level, the teque (triple-ended queue)!

The teque supports the following four operations:

  1. push_back x: insert the element $x$ into the back of the teque.

  2. push_front x: insert the element $x$ into the front of the teque.

  3. push_middle x: insert the element $x$ into the middle of the teque. The inserted element $x$ now becomes the new median element of the teque, where the median is defined as the $((\textrm{size of teque})+1) / 2$ indexed element ($0$-based).

  4. get i: prints out the $i^\textrm {th}$ index element ($0$-based) of the teque.

Input

The first line contains an integer $N$ ($1 \le N \le 10^6$) denoting the number of operations for the teque. Each of the next $N$ lines contains a string $S$, denoting one of the above commands, followed by one integer $x$. If $S$ is a push_back, push_front, or push_middle command, $x$ ($1 \leq x \leq 10^9$), else for a get command, $i$ ($0 \leq i \leq (\textrm{size of teque})-1$). We guarantee that the teque is not empty when any get command is given.

Output

For each get i command, print the value inside the $i^\textrm {th}$ index element of the teque in a new line.

Warning

The I/O files are large. Please use fast I/O methods.

Sample Input 1 Sample Output 1
9
push_back 9
push_front 3
push_middle 5
get 0
get 1
get 2
push_middle 1
get 1
get 2
3
5
9
5
1