401439: GYM100451 H Polycarpus VS Dequeue

This is an interactive problem, so don't forget to perform a flush operation after each line of output. As the problem is interactive, you can process another query only after you've printed the answer to the previous one.

During the IT lessons, Polycarpus studied many data structures: stacks, queues, dequeues and even heaps. It's time to have the exam!

Polycarpus got a question on dequeues and the boy answered the question brilliantly. He began from a beautiful phrase: "In computer science, a double-ended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list."

Now it's time to do the practical part of the question. The teacher is sure that if a student knows a data structure well, then he can emulate its behavior in his mind without any problems.

Now Polycarpus is standing at the whiteboard divided into 10⁹ lines. They are numbered from 1 to 10⁹ from top to bottom. Each line is either empty or it contains a dequeue operation. Here is a list of possible operations:

• «push_front x» — add element x to the beginning of the dequeue,
• «push_back x» — add element x to the end of the dequeue,
• «pop_front» — remove an element from the beginning of the dequeue,
• «pop_back» — remove an element from the end of the dequeue.

At the beginning of the practical task, Polycarpus is standing in front of the empty whiteboard and the teacher checks his knowledge by saying the commands of type:

• "Let's write the following operation to the line i ..." (names a specific operation),
• "Now let's remove an operation from the line i",
• "Tell me, what elements will be on the ends of the dequeue, if starting from an empty dequeue, we execute all lines, on by one, from the first to the i-th one?".

Thus, the task for Polycarpus isn't that easy after all! The teacher has a luxuriant imagination, so he names the commands very quickly and they go in an unpredictable order.

Polycarpus couldn't cope with the given task but he volunteered to make a program that will process the queries of the three types. Having written such program, he got the mark he wanted, "A".

We ask you to repeat Polycarpus' achievement and implement the program that processes queries.

The first line of the input contains integer n (1 ≤ n ≤ 4·10⁵) — the number of the queries. Then follow n lines of one on the following types:

• "i OPERATION" — fill the line i with operation "OPERATION",
• "i -" — remove an operation from the i-th line,
• "i ?" — name the dequeue's elements on the end after executing the operations from top to bottom by the moment you stop after processing the line i.

The teacher always maintain correct state of the dequeue, that is:

• if you need to fill the line i, then it's empty at that moment,
• if you need to remove an operation from the line i, then this line contains an operation at that moment,
• after each query, the sequential execution of all operations from the first to the last line doesn't call pop_front/pop_back from an empty dequeue.

Values x for operations "push_front x" and "push_back x" are integers from 1 to 10⁹, inclusive.

As the problem is interactive, you can read a query only after you've printed the output to the previous one.

After you process each query, print a line with two numbers. Print line "0 0" after you process queries that add/remove operations. Print line "front back" after you process a request of type '?', where front is the value from the begin of the dequeue and back is the value from its end. Print "-1 -1" if the dequeue is empty.

Don't forget to execute the flush operation after you've printed each line of the output.

9
1 push_back 10
2 push_front 20
2 ?
1 -
2 ?
1 push_back 30
3 pop_front
3 ?
2 ?

0 0
0 0
20 10
0 0
20 20
0 0
0 0
30 30
20 30

11
20 push_back 4
20 ?
40 pop_back
40 ?
30 push_back 3
30 ?
10 push_front 1
10 ?
20 ?
30 ?
40 ?

0 0
4 4
0 0
-1 -1
0 0
4 3
0 0
1 1
1 4
1 3
1 4

Because of poor performance of interactive queries testing, input data will be written in the solution input stream by blocks. The total number of blocks does not exceed 1000. Each block contains one or more queries. We do not specify the method how queries are divided into blocks.