#C2889. Reconstruct the Original Message

    ID: 46254 Type: Default 1000ms 256MiB

Reconstruct the Original Message

Reconstruct the Original Message

You are given a dictionary of valid English words and a corrupted message string. The corrupted message contains lowercase letters and the wildcard character '?' which can represent any single letter. Your task is to determine if there exists a word in the dictionary that matches the pattern of the corrupted message exactly. A match is defined as having the same length as the corrupted message and having identical characters at all positions where the corrupted message has a letter (i.e. not a '?').

If such a word exists, output two lines: the first line should be "YES" and the second line the matched word. If no match is found, simply output "NO".

The matching should be performed in the order in which the dictionary words are provided, and the first valid match should be returned.

Note: If there are multiple valid words (especially in cases where the corrupted message is entirely '?'), returning any one valid match is acceptable.

inputFormat

The input is read from the standard input (stdin) and has the following format:

  1. The first line contains an integer n, representing the number of words in the dictionary.
  2. The second line contains n space-separated words.
  3. The third line contains the corrupted message string, which consists of lowercase letters and '?' wildcards.

outputFormat

Print the result to the standard output (stdout). If a matching word is found in the dictionary, output "YES" on the first line followed by the matched word on the second line. If no matching word exists, output "NO".## sample

3
hello world happy
h?ll?
YES

hello

</p>