First non-repeating character

Problem

A product code is a string of letters. Find the first character in it that appears exactly once, and print it. If every character repeats, print NONE.

Input, output and limits

Input: One line with the code (no spaces).
Output: The first character that appears exactly once, or NONE.
Constraints: 1 ≤ length ≤ 100000
Capital and small letters are different characters

Examples

Example 1

Input

swiss

Output

s appears 3 times; w appears once and comes first among the single ones.

Example 2

Input

aabbcc

Output

NONE

Every character repeats.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Pass 1: count every character. Pass 2: walk the string again and stop at the first character whose count is 1.

Hint 2

A LinkedHashMap keeps the characters in order of first appearance, so the first entry with count 1 is the answer.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Maps problems

Problem

Input, output and limits

Examples

Hints

More Maps problems