21. Odd Balloon Colour

Difficulty: easy · Hashing, String

Problem

A street vendor at a fun fair has a bunch of `N` balloons, each with a colour written as a single letter. Find a colour that appears an **odd** number of times. If more than one colour appears an odd number of times, print the one whose first occurrence comes earliest in the array. If every colour appears an even number of times, print `All are even`.

Input

- Line 1: the integer `N`. - Line 2: `N` space-separated single letters `B[0] ... B[N-1]`.

Output

Print the colour letter, or the exact message `All are even`.

Example 1

Input:
7
r g b b g y y
Output:
r

Explanation: r appears once (odd); g, b and y appear twice each, so r is printed.

Example 2

Input:
10
a b b b c c c a f c
Output:
b

Explanation: b (3 times) and f (once) are odd; b occurs first in the array.

Example 3

Input:
4
x y y x
Output:
All are even

Explanation: x and y both appear twice, so every colour is even.

Constraints

- 1 <= N <= 10^5 - Every `B[i]` is a letter; all letters in one input are of the same case (all lowercase or all uppercase)

Solutions are judged against 3 sample and 9 hidden tests. Sign in to solve it · All problems