You may have heard of a queue or a double-ended queue... but have you heard of a triple-ended queue?

The triple-ended queue is a new groundbreaking queue-like data structure with three locations to insert and remove from! It builds on the double-ended queue, being able to remove and add elements to either end in constant time. The third "end" of this queue is right in the middle! More specifically, removing from the "middle" means removing from the element at index ~\lfloor \frac{n}{2} \rfloor~ (where ~n~ is the number of elements in the triple-ended queue before removal). Inserting an element in the middle will cause all elements initially at indices ~\lfloor \frac{n}{2} \rfloor~ or greater of the original array to move to the right, and index ~\lfloor \frac{n}{2} \rfloor~ of the new queue (with ~n~ in this case being the number of elements after the element is inserted) will be the new element. The queue is ~0~-indexed.

There are ~6~ operations to be supported by this triple-ended queue:

• pop left remove the left-most element in the queue.
• pop right remove the right-most element in the queue.
• pop middle remove the middle element in the queue.
• append left x append an integer x to the left of the queue.
• append right x append an integer x to the right of the queue.
• append middle x inserts an integer x to the middle of the queue.

Like the queue and double-ended queue, removals and insertions in this triple ended queue should be in constant time. Can you implement the triple-ended queue?

Input Specification

The first line will contain an integer ~N\:(1\le N \le 10^6)~, indicating the starting number of integers in the triple-ended queue.

The next line will contain ~N~ spaced integers, where the ~i~-th element is an integer ~a_i\:(1 \le a_i \le 10^5)~.

The next line will contain an integer ~Q\:(1\le Q \le 10^6)~, indicating the number of operations that will be performed.

Each of the next ~Q~ lines will be in the format of one of the operations described above.

The number of elements in the triple-ended queue will never exceed ~10^6~ nor be less than ~1~ at any given time.

Output Specification

For each pop operation, output the element that was removed from the triple-ended queue.

Sample Input 1

5
2 1 5 3 4
9
pop left
pop middle
append right 6
append right 7
pop middle
append left 8
append middle 9
pop right
pop middle

Sample Output 1

2
3
4
7
5

Explanation for Sample Output 1

The contents of the triple-ended queue are updated as follows:

~[2,1,5,3,4]\rightarrow[1,5,3,4]\rightarrow[1,5,4]\rightarrow[1,5,4,6]\rightarrow[1,5,4,6,7]\rightarrow[1,5,6,7]\rightarrow[8,1,5,6,7]\rightarrow[8,1,5,9,6,7]\rightarrow[8,1,5,9,6]\rightarrow[8,1,9,6]~

Sample Input 2

2
1 2
7
append right 3
append left 4
pop middle
pop middle
pop middle
append middle 5
pop right

Sample Output 2

2
1
3
5