First Non-Repeating Character

Given a string s, your task is to find the first non-repeating character in it. If every character repeats, output an underscore ('_'). The solution should efficiently determine the character using optimal time complexity techniques. Note that if the input string is empty or every character occurs more than once, you must output '_' (underscore).

Example:

• For input "abacabad", the output is 'c' because 'c' is the first character that does not repeat.
• For input "abacabaabacaba", the output is '_' because every character repeats.

Your solution should handle any printable characters including symbols.

inputFormat

The input consists of a single string s provided via standard input (stdin). The string may contain letters, digits, special characters, or be empty.

outputFormat

Output a single character to standard output (stdout): the first non-repeating character in s. If there is no such character, print an underscore ('_').

abacabad

c