Deli Deli

Interview

Time limit1sMemory limit128 MB

Summary

For each of N words, apply the first matching pluralization rule from a list of irregular forms and four suffix rules, then print the result.

Level: Easy2 of 10
Topics: String, Hash map, Implementation, Brute force
Solved: No attempts yet

Problem

Mrs. Deli runs the delicatessen store "Deli Deli". Last year she decided to expand her business and open an online store, hiring a programmer who built it for her.

Recently some of her new online customers complained about the electronic bills: the programmer forgot to use the plural form when an item is purchased multiple times. Unfortunately that programmer is now on holiday, so it is your task to implement this feature. Here is how to form the plural of a word:

If the word is in the list of irregular words, replace it with the given plural.
Otherwise, if the word ends in a consonant followed by "y", replace that "y" with "ies".
Otherwise, if the word ends in "o", "s", "ch", "sh", or "x", append "es" to the word.
Otherwise, append "s" to the word.

Check the rules in order from 1 to 4 and apply only the first one that matches.

Input

The first line contains two integers $L$ and $N$ ( $0 \le L \le 20$ , $1 \le N \le 100$ ). The next $L$ lines describe the irregular words and their plural forms. Each such line contains two words separated by a space, where the first word is the singular form and the second word is the plural form of an irregular word. After the list of irregular words, $N$ lines follow, each containing one word that you must turn into its plural form. Each word consists of at most 20 lowercase letters from the English alphabet ('a' to 'z').

Output

Print $N$ lines. The $i$ -th line must contain the plural form of the $i$ -th input word.

Examples1

Example 1

Input

3 7
rice rice
spaghetti spaghetti
octopus octopi
rice
lobster
spaghetti
strawberry
octopus
peach
turkey

Expected output

rice
lobsters
spaghetti
strawberries
octopi
peaches
turkeys