Problem

Data Manager is a sophisticated data structure, which manages a set of data and fulfills operations on the data set. There are 3 kinds of operations:

Given a list of operations, you are to predict the output of the Data Manager. At the beginning, the Data Manager is empty.

Input

There is only one test case. In the first line, an integer T (T <= 500000) will be given, which is the number of operations. The next T lines contains T operations.

Output

Give output of the Data Manager, one query per line.

Sample Input

10
add 1
add 100
add -1
query
delete
query
add 2046
query
delete
query

Sample Output

-1
1
1
100


Author: wiltord