You have a bucket of numbers which is initially empty. You have to perform Q operations of 4 different types explained below.
Type 1: 1 X. Insert the number X in your bucket, if that number is not already there.
Type 2: 2 X. Remove the number X from the bucket, if that number exists in your bucket.
Type 3: 3 X. Remove all numbers from the bucket which are smaller than X.
Type 4: 4 X. Remove all numbers from the bucket which are greater than X.
After performing all the Q operations, you have to print all the remaining numbers which exist in the bucket. Print them in the order of their insertion.
Input
The first line of the input contains a single integer Q.
Each of the next Q lines contains two integers P and X, where P is the type of the operation and X is the number explained above.
Constraints:
1 ≤ Q ≤ 105
1 ≤ P ≤ 4
-109 ≤ X ≤ 109
Output
After doing all the operations, print the remaining numbers in the bucket in the order of their insertion in one line. "Print in the order of insertion" means number A will be printed before number B only if A was inserted in the bucket before B. Print nothing if your bucket is empty at the end.
Sample
| Input | Output |
|---|---|
9 1 1 1 2 1 3 1 4 2 1 3 3 4 3 1 2 1 3 | 3 2 |
Explanation of Sample Case:
1st operation: insert 1 in your bucket, as 1 is not present in your bucket.
2nd operation: insert 2 in your bucket, as 2 is not present in your bucket.
3rd operation: insert 3 in your bucket, as 3 is not present in your bucket.
4th operation: insert 4 in your bucket, as 4 is not present in your bucket.
5th operation: remove 1 from your bucket as 1 is present in your bucket.
6th operation: remove all numbers from your bucket which are smaller than 3. So only 2 will be removed.
7th operation: remove all numbers from your bucket which are greater than 3. So only 4 will be removed.
8th operation: insert 2 in your bucket, as 2 is not present in your bucket.
9th operation: it says you to insert 3, but you can’t do that as 3 is already present in your bucket.
Now you will print the remaining numbers, which are 3 and 2. 3 will be printed before 2 as it was inserted earlier.
