The Adelaide Competitive Programming Club is hosting a pizza party! After ordering and carrying all the pizzas to the room, Shahid isn't going to let greedy students take all of the pizza for themselves. The last time the club hosted a pizza party, students could only join the queue once to get pizza. However, there were still some leftovers, so Shahid modifies the rule. Students may join the queue for pizza for a second time, but only if everyone else in the room has gotten their pizza. They cannot, however, rejoin the queue more than once.

He knows that there are sneaky students that will try to break the rules, so he comes up with a plan. While he guards the pizza, he tries to get his friend Justin to code up a solution to check if any students are breaking the rules. Unfortunately, Justin is busy eating pizza so you'll have to come up with the solution instead.

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^6)~, the number of people in the queue. The next ~n~ lines consist of a string ~S~ ~(1 \leq S.\text{length} \leq 100)~, representing the name of the person in the queue. The string ~S~ contains uppercase and lowercase English characters.

Output

Output the name for every instance where someone rejoins the queue despite not everyone having gone at least once, or rejoins the queue more than once. Make sure that the names are outputted in order.

Clarifications

• If someone breaks two rules at the same time, their name should only be printed once.

Example

Input 1

5
Nic
Bob
Alice
Nic
Sam

Output 1

Nic

Nic rejoined the queue before Sam, so he broke the rule of rejoining be queue after everyone has gone at least once.

Input 2

10
Nic
Bob
Alice
Sam
Brooke
Bob
Jason
Nic
Bob
Nic

Output 2

Bob
Bob
Nic

First, Bob broke a rule by entering the queue before everyone has gone at least once. Then, Bob breaks a rule again by rejoining the queue more than once. Nic then rejoins the queue more than once as well.