Advanced Data Structures
A. Persistent Deque
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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.

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

B. Order Maintenance Structure
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You should implement a list that allows the following operations:

  • < x — Given x not in the list, insert x in the beginning of the list.
  • I x y — Given y not in the list and x in the list, insert y after the element x.
  • D x — Given x in the list, remove element x from the list.
  • O x y — Given x and y in the list, return YES if x comes before y in the list, or NO otherwise.

Initially, the list is empty.

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 ≤ 2·105
  • For all queries, x and y will be between 1 and 2·105.
Output

For each query of type O, print YES or NO, the value returned. Don't forget to flush the output.

Examples
Input
5
< 1
< 2
O 1 2
I 2 10
O 10 1
Output
NO
YES
Input
10
< 1
I 1 2
I 1 3
I 1 4
I 1 5
I 1 6
I 1 7
O 7 6
O 3 7
O 6 4
Output
YES
NO
YES

C. Retroactive Queue
time limit per test
2 seconds
memory limit per test
64 MB
input
standard input
output
standard output

Your task is to implement a retroactive queue.

A data structure is retroactive if it allows insertion and removal of operations in the past, and also queries. Informally, is like you went to the past, changed the structure, and the change propagated to the present (like some bad fiction movie).

An usual queue should support modifications enqueue(x), that adds the element x to the end of the queue, and dequeue(), that removes the first element of the queue.

You must deal with the following queries:

  • + t E x — Insert the modification enqueue(x) at time t.
  • + t D — Insert the modification dequeue() at time t.
  • - t — Remove the modification at time t.
  • Q t k — Print the k-th element of the queue in time t (1-indexed).

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

On the first line, a single integer Q, the number of queries.

Each of the next Q lines have a query, in the format given in the statement.

Limits

  • 1 ≤ Q ≤ 3·105
  • For all queries, 1 ≤  t  ≤ 109. An operation is never inserted at a time that has another operation already.
  • In + t E x queries, x will fit in a 32-bit signed integer.
  • In - t queries there will be a query at time t.
  • In Q t k queries, k will be between 1 and the current queue size at time t.
  • All dequeue() are valid at all times. That means there's never a dequeue() operation on an empty queue.
Output

For each Q t k query, print its answer.

Examples
Input
5
+ 1 E 1
+ 2 E 2
Q 2 1
- 1
Q 2 1
Output
1
2
Input
11
+ 10 E 10
+ 200 E 5
Q 201 1
+ 5 E 1
Q 201 1
+ 7 D
Q 201 2
- 7
Q 199 1
Q 200 2
Q 201 3
Output
10
1
5
1
10
5
Note

On the first sample, 1 and 2 are added to the queue, and then the insertion of 1 is removed.