Percy the peacock is quite the fancy peacock, and loves to go to peacock parties! For each party, he adorns a set of colorful feathers to look his best.
However, he recently realized that despite owning many different colors, Percy only wears a handful of colors. The problem is, Percy leaves all his colorful feathers in a pile – taking the top one off when he attends a party, and putting it back on top when he's done. In fact, the only time the color he wears ever changes is when he buys a new set of feathers!
Instead of taking from the top of the pile, Percy has now decided to take his next set of feathers from the bottom of the pile, in the hopes that he can go show off all his colors at the peacock parties. Can you help him figure out what colors he will wear to each party?
The first line of input is a single integer, $$$1 \leq n \leq 2 \cdot 10^5$$$, denoting the number of days.
Then, follow $$$n$$$ lines, where the $$$i$$$th line contains what Percy does on the $$$i$$$th day. This will be one of:
- $$$1$$$ $$$c$$$: Percy buys a set of feathers with color $$$c$$$, which is a string of at most 10 characters. These feathers go on the top of the pile.
- $$$2$$$: Percy attends a party with the bottommost set of feathers, and puts them back on top of the pile after he comes back from the party. It is guaranteed that the pile is not empty when this happens.
For each day when Percy attends a party, output the color of the feathers he wears to the party.
10 1 red 1 blue 1 green 2 2 1 yellow 2 2 2 2
red blue green red blue yellow
