Mr. N, a kind CS teacher, has decided to give out presents to his hard working students! He has decided that a harder working student should get priority over a student that has slacked off. Unfortunately, some of Mr. N's students are trolls, and Mr. N will remove them from his list if he sees fit. Hoping to move up Mr. N's list, you decide to write a program to order the list.
The first line will have an integer ~Q~ ~(1 \le Q \le 10^5)~, the number of queries that follow.
Lines ~2 \dots Q + 1~ will each contain one of three possible queries:
F x: add student ~x~ to the beginning of the list
E x: add student ~x~ to the end of the list
R x: remove student ~x~ from the list. ~x~ is guaranteed to be a student already in the list.
~x~ is an integer ~1 \le x \le 10^9~.
Output the list, from beginning to end, with each number on a new line. It is guaranteed that the list will only contain distinct integers.
For ~20\%~ of points, ~Q \le 1\,000~ and each ~x~ satisfies ~1 \le x \le 10^6~.
5 F 1 F 2 R 1 E 3 E 1
2 3 1