First colour with an odd count

Balloons of different colours are listed in order. Print the first colour (by first appearance) that appears an odd number of times. If every colour appears an even number of times, print "All are even".

Reported in: TCS NQT (Sep 2023) (memory-based)

Input

First line: N. Second line: N colour names.

Output

A colour name, or All are even.

Constraints

1 ≤ N ≤ 10^5.

Example 1

Input:
6
red blue red green blue blue

Output:
blue

Example 2

Input:
4
red red blue blue

Output:
All are even

Hint: Count with a dictionary, then walk the list again in order of first appearance.

All coding practice