403758: GYM101261 A Persistent Deque

A. Persistent Dequetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A persistent data structure is a data structure in which you can modify and access any previous version of the data structure. The k^th query will create version k of the data structure. Your task is to implement a persistent deque, each query copies an old version of the structure and then modifies it. You need to process the following queries:

• B v x — Add x to the beginning of the deque with version v.
• E v x — Add x to the end of the deque with version v.
• < v — Remove the first element of the deque with version v.
• > v — Remove the last element of the deque with version v.

Assume version 0 is an empty deque. Every query creates a new version of the deque.

All queries are online, that means you should flush the output before reading the input for the following query. Use fflush(stdout) for C/C++.

Input

In the first line an integer Q, the number of queries. Each of the next Q lines has a query, in the format given in the statement.

Limits

• 1 ≤ Q ≤ 3·10⁵
• In the ith query it is guaranteed that 0 ≤ v < i
• For each query of type B or E, x will fit in a 32-bit signed integer
• For each query of type < or >, it is guaranteed the deque with version v will not be empty

Output

For each query of type < or >, print the element removed.

Interaction

Remember to flush the output after every answer.

ExampleInput

8
B 0 10
E 0 -10
< 2
> 1
E 2 5
> 5
< 6
< 2

Output

-10
10
5
-10
-10