题目描述

After solving the problem given by the Phantom Ensemble, Youmu continues on her way.

Now, she meets Alice, the master of the dolls.

Though Alice is a master of the dolls, she also has some problems with her dolls as there are too many of them.

She needs to come out a way to operate these dolls more efficiently. Now the dolls are in a queue from front to back.

Some time, Alice needs to add one doll into the front of the queue or the back of the queue, and every doll has a value expressing their beauty.

And for some time, Alice need to pop one doll from the front of queue or the back of the queue.

What is the most important is that, she needs to know the maximum and minimum beauty after each operation( add or pop from the queue).

Now she sees Youmu coming, she just gives Youmu this problem. Youmu also, solved the problem quickly, can you solve the problem too?

picture: Alice with her dolls

输入格式

First line of the input contains two positive integers $N,M (1\\le M,N\\le 200000)$ $N$ indicates the original size of the queue, and $M$ indicates the number of operations needed.

Then next line follows $N$ positive integers $a[i] (1\\le a[i]\\le 10^9)$ indicating the beauty of the dolls in the original queue.

Then follows $M$ lines, each line contains one operation as below:

$POP$ $FRONT$ means pop the queue from the front. If the queue is empty, do nothing.

$POP$ $BACK$ means pop the queue from the back. If the queue is empty, do nothing.

$PUSH$ $FRONT$ $a[i]$ means push one doll with beauty $a[i]$ to the front of the queue.

$PUSH$ $BACK$ $a[i]$ means push one doll with beauty $a[i]$ to the back of the queue.

输出格式

After each operation print two numbers indicating the minimum beauty and the maximum beauty in the queue.

If the queue is empty after some operations, just print one line with EMPTY.

样例

12 12 
2 3 1 12 9 9 8 4 14 15 5 5 
POP BACK 
POP BACK 
PUSH FRONT 100 
PUSH BACK 20 
POP FRONT 
POP FRONT 
POP FRONT 
POP FRONT 
PUSH BACK 100 
POP BACK 
POP BACK 
PUSH FRONT 1

1 15 
1 15 
1 100 
1 100 
1 20 
1 20 
1 20 
4 20 
4 100 
4 20 
4 15 
1 15 

1 3 
2 
POP BACK 
POP FRONT 
PUSH BACK 10

EMPTY 
EMPTY 
10 10