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.