403189: GYM101063 G Job List

As you may already know, there are a lot of scientists working on Mars. They come from various different fields of studies, all very excited with the exploration. Nevertheless, right now, they decided to go on strike and have not done any work for the past two weeks.

What they've been complaining about for quite a while is that there is only one super computer on the whole planet, so the waiting list is huge and sometimes they have to wait for months in order to use it. As an attempt to calm the scientists a little, GEMA decided to implement a new policy for the waiting list: When a job is added, it is placed on the top of the list. If a job is changed, it is moved to the top of the list as well.

Even though this policy would be considered stupid by most, the scientists decided to try it, but you know, scientists are very devious people (specially GEMA scientists). Quite soon they began to use time traveling machines to go back and forth in time and change other scientists' jobs, making them go to the top of the list, or even removing them from the list. Now your task is to implement something that could process some queries for the waiting list. There are 4 types of queries:

• t 'c' jobid: at time t move the job whose id equals jobid to the top of the list, if there are no jobs with this id, create it and add it to the list.
• t 'r' jobid: at time t remove the job whose id equals jobid from the list
• t 'f': print the id of the first job in the list (top) at time t
• t 's': print the id of the second job in the list at time t

t, jobid are integers and 'c','r','f','s' represent the characters themselves, see the sample test cases for better understanding.

Initially, at time 0, there are no jobs in the list.

A job will be removed from or added to the list only once. However, the creation time can change (take a look at the second example).

To process the i-th query with time t_i, you must consider the actions of the queries 1, ..., i - 1 with time t ≤ t_i. If there are two queries i and j, with i < j and t_i = t_j, you must consider the action of the ith query first.

If you are processing a query that requests the removal of a job at time t, you may assume that there has been a query that created this job at a time t' ≤ t. You can also assume that there won't be any queries for this job with time t' > t and that the following queries for this job (if any) will have t' < t.

The input starts with an integer Q(1 ≤ Q ≤ 5000). Then follow Q lines, each with a query following the format described above (1 ≤ t, jobid  ≤ 10⁹).

For each query of type 'f' and 's' print the id of the job which satisfies the condition of the query asked, or print  - 1 if there is no job which satisfies the condition of the query.

5
3 c 1
10 f
4 r 1
10 f
3 f

1
-1
1

6
5 c 1
6 c 2
3 f
1 c 2
1 c 1
3 s

-1
2

9
5 c 7
2 f
1 c 8
2 f
3 c 7
5 s
10 f
9 r 7
10 f

-1
8
8
7
8

10
1 c 1
1 c 2
1 c 3
1 f
1 c 1
1 c 2
1 s
1 r 3
2 c 1
2 f

3
1
1

In the first sample, the first query adds the job 1 to the list at time 3. Then, it is asked what is the first job in the list at time 10, which is job 1, (notice that to answer this query you just consider the queries you have already processed).

Query 3 says that at time 4, job 1 is removed. The fourth query asks the same as the second query, but now as the past was changed by the third query, there are no jobs at time 10.

The last query, we are at t = 3, which the only job in the list hasn't been removed yet, so the answer is 1.