Deque 2

Implement a deque that stores integers, then write a program that processes the commands given as input.

There are eight kinds of commands.

1. 1 X: Inserts the integer X at the front of the deque. (1 ≤ X ≤ 100,000)
2. 2 X: Inserts the integer X at the back of the deque. (1 ≤ X ≤ 100,000)
3. 3: If the deque has an integer, removes the front integer and prints it. Otherwise, prints -1.
4. 4: If the deque has an integer, removes the back integer and prints it. Otherwise, prints -1.
5. 5: Prints the number of integers in the deque.
6. 6: Prints 1 if the deque is empty, otherwise 0.
7. 7: If the deque has an integer, prints the front integer. Otherwise, prints -1.
8. 8: If the deque has an integer, prints the back integer. Otherwise, prints -1.

The first line contains the number of commands N. (1 ≤ N ≤ 1,000,000)

Each of the following N lines contains one command.

At least one command asks for output.

For each command that asks for output, print the result on its own line.