Word Replacement

You are given a list of words and a dictionary mapping certain words to their replacement values. Your task is to replace each word in the list with its corresponding value from the dictionary. If a word does not exist in the dictionary, you should replace it with UNKNOWN.

The input consists of the number of words, the list of words, the number of dictionary entries, and the dictionary entries. For every word, if a replacement exists, output the replacement; otherwise, output UNKNOWN.

The problem can be mathematically formulated as follows:

Given a list \(W = [w_1, w_2, \dots, w_T]\) and a dictionary \(D\) where each key \(k\) maps to a value \(v\), compute the list \(R = [r_1, r_2, \dots, r_T]\) where \[ r_i = \begin{cases} D(w_i) & \text{if } w_i \in D,\\ \text{\texttt{UNKNOWN}} & \text{otherwise.} \end{cases} \]

inputFormat

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

• The first line contains an integer T denoting the number of words.
• The second line contains T space-separated words.
• The third line contains an integer N, the number of dictionary entries.
• The following N lines each contain two space-separated strings: a key and its corresponding value.

outputFormat

Output a single line to standard output that contains the replaced words separated by a single space. For each word in the input list, if it exists in the dictionary then its replacement is used; otherwise, output UNKNOWN.

4
apple banana cherry date
3
apple fruit
banana fruit
cherry fruit

fruit fruit fruit UNKNOWN