Double-Ended Queue Operations

You are given m double-ended queues and must perform q operations on them. The operations are defined as follows:

• push_back(a,x): Insert the element x at the back of the a-th deque, i.e. append to the tail.
• pop_back(a): Remove the element from the back of the a-th deque. If the deque is empty, skip the operation.
• push_front(a,x): Insert the element x at the front of the a-th deque, i.e. add to the head.
• pop_front(a): Remove the element from the front of the a-th deque. If the deque is empty, skip the operation.
• size(a): Output the number of elements in the a-th deque.
• front(a): Output the front element of the a-th deque. If the deque is empty, do nothing.
• back(a): Output the back element of the a-th deque. If the deque is empty, do nothing.

Note that for the operations pop_back, pop_front, front and back, if the corresponding deque is empty, the operation is simply skipped.

The parameters satisfy the following: $1 \leq a \leq m$ and the operations are executed in the given order.

inputFormat

The first line contains two integers $m$ and $q$, where $m$ is the number of deques and $q$ is the number of operations.

The following $q$ lines each contain one operation in one of the following formats:

• push_back a x
• pop_back a
• push_front a x
• pop_front a
• size a
• front a
• back a

outputFormat

For each query operation that produces output (i.e. size, front, and back), output the resulting value on a separate line in the order of execution. If a front or back operation is executed on an empty deque, do not output anything for that operation.

sample

2 8
push_back 1 10
push_front 1 5
size 1
front 1
back 1
pop_front 1
pop_back 1
size 1

2
5
10
0