403758: GYM101261 A Persistent Deque

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 kth 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·105
  • 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

加入题单

上一题 下一题 算法标签: