YJJ’s Stack

Problem Description

As it’s known to all, there’s a cute girl named YJJ living in Sand River. One day when he was learning stack, he suddenly thought that it would be more interesting to add timestamp to each stack command, and wanted to delete the element(even it’s not the top one) as he wanted. So he invented a stack called "YJJ's stack", which supports the following four command:

● push v t – push $v$ into YJJ’s stack, whose timestamp is $t$ ;

● delete v t – delete the uppermost element from the stack which is equal to $v$ , whose timestamp is $t$ ;

● pop t – pop the top element from YJJ’s stack, whose timestamp is $t$ ;

● query t – execute a query operation which is described below, whose timestamp is $t$ ;

There is an empty set of commands initially. When an command except query t arrives, we put the command into the set. When an command query t arrives, we process as follows:

1. Clear YJJ's stack .
2. Execute the command currently in the set whose timestamp is less than t .
3. The executing order of command is ordered by their timestamp in ascending order.
4. Print the top element in the stack. Records of command are in arriving order, you are required to execute according to above rules. Another three constraints are made to simplify the problem :
5. All the pop and delete command are valid. In another word, if you do the process correctly, pop command will not be excuted on an empty YJJ’s stack and delete v command will not be excuted on an YJJ’s stack without v .
6. All timestamps are different.
7. The number of pop command is no more than $5$.

Input

The first line of the input contains an integer $T$ $(1≤T≤10)$,which is the number of test cases. In each case, the first line of the input contains an integer $N$ $(1≤N≤1.2\times 10^5)$. The following $N$ lines each contain an command in one of the following four formats: push v t , delete v t , pop t , query t , where $1≤v≤5, 0≤t≤10^9$, and $v, t$ are integers. The command are given in the order in which they arrive.

Output

For each query command, output the answer in a line. If the stack is empty, output $-1$ instead.

Sample Input

2
13
push 2 10
push 1 20
query 21
delete 2 30
query 31
push 3 40
query 53
pop 60
query 62
push 2 70
query 41
push 1 50
query 91
9
push 2 10
push 1 20
query 11
query 21
delete 2 30
query 31
query 12
pop 40
query 41

Sample Output

1
1
3
1
3
2
2
1
1
2
-1

Source

2018 Multi-University Training Contest 7