You own a cafeteria, and you just found out that one of your customers had chicken pox, which is extremely contagious. In your cafeteria, trays are not washed, and you want to warn any people who may have been affected by his contaminated tray. The infected customer was the very first customer of the day. The cafeteria has one infinite tray stack, and customers get trays from and return trays to the top of the stack without any cleaning. Each tray has two sides, each of which can be infected or not infected. People can infect trays, trays can infect people, and trays can infect each other. Here is a list of exactly what actions can transmit the virus:
● If an infected person takes a tray, that tray becomes infected on both sides.
● If any person takes a tray that is infected on either side, that person becomes infected and spreads the infection to both sides of the tray.
● When a tray infected on the bottom is returned to the tray stack, it is placed on top of another tray, whose top side then becomes infected.
● If any tray is returned to the stack and placed on top of another tray whose top side is infected, the bottom of the new tray is infected.
You know the order in which all the customers took and returned trays that day. Warn the infected customers by printing out the names of the infected customers.
● If an infected person takes a tray, that tray becomes infected on both sides.
● If any person takes a tray that is infected on either side, that person becomes infected and spreads the infection to both sides of the tray.
● When a tray infected on the bottom is returned to the tray stack, it is placed on top of another tray, whose top side then becomes infected.
● If any tray is returned to the stack and placed on top of another tray whose top side is infected, the bottom of the new tray is infected.
You know the order in which all the customers took and returned trays that day. Warn the infected customers by printing out the names of the infected customers.
Input Format
Line 1: a single integer n indicating the number of tray actions taken by customers.Lines 2 ≤ i ≤ n + 1: consist of the tray action and the person’s name, in the form “x y” where x is a ‘t’ if the customer takes a tray and ‘r’ if the customer returns a tray, and y is the name of the customer.
Sample Input
3
t Bob
r Bob
t Jack
Output Format
Output the names of each customer infected, with each customer’s name on a new line. The customers should be ordered by when they took their tray, with names of customers who took trays earlier printed before names of customers who took trays later.
The output is to be formatted exactly like the sample output given below.
Sample Output
Bob
Jack
You must be logged in to submit a solution.