The Adelaide Competitive Programming Club is providing sushi for its hard-working members after another round of AUCPL. After ordering and carrying all of the sushi boxes to the room, Shahid isn't going to let greedy students take all of the sushi for themselves.

He creates a rule: students must only join the queue to get sushi once, and no hoarding! However, he knows that there are sneaky students that will try to join the queue a second time so he comes up with a plan. While he guards the sushi, he tries to get his friend Justin to code up a solution that will check if someone has already gotten their sushi or not. Unfortunately, Justin is busy eating sushi 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)~ that represents the number of people in the queue. The next ~n~ lines have a string ~S~ ~(1 \leq S.\text{length} \leq 100)~ that represents the name of the person in the queue. The string ~S~ contains uppercase and lowercase English characters.

Output

Output the names of the people who have entered the queue more than once, every time they rejoin the queue. The names should be in the order that they appear in the input.

Example

Input 1

4
Nic
Bob
Alice
Nic

Output 1

Nic

Nic rejoined the queue once.

Input 2

6
Nic
Bob
Alice
Nic
Bob
Nic

Output 2

Nic
Bob
Nic

Bob rejoined the queue once, while Nic rejoined the queue twice.