Designing a Data Structure

Data structure is one of your favourite topics, isn't it? Let’s design a new data structure!

In this new data structure, there will be a list and some operations.
The operations are :

• Insert Front X — Insert X into the front of the list.
• Insert Back X — Insert X into the back of the list.
• Erase Front — Erase the first element of the list.
• Erase Back — Erase the last element of the list.
• Get Front — Print the first element of the list.
• Get Back — Print the last element of the list.
• Get Max — Print the maximum element of the list.
• Get Min — Print the minimum element of the list.

You need to design a data structure as described above and perform Q operations.

Input

The first line of the input will contain a single integer Q, denoting the number of operation.

The next Q lines will contain any of those operations described above.

Constraints

1 ≤ Q ≤ 10^5
1 ≤ X ≤ 10^6

Output

Perform each operation as described in the problem statement.

Sample

8
Insert Back 8
Get Front
Insert Front 9
Get Max
Erase Back
Insert Back 3
Get Back
Get Min

8
9
3
3

Assume that, every operation will be valid.