Nowadays, Sanvi is learning the English alphabet. She had already mastered A, B, C and D, but is still struggling with other remaining letters. So whenever you ask her a question related to A-B-C-D , she can reply very quickly. She can only reply to the following four questions:
A for ? B for ? C for ? D for ?
You are given a dictionary which she had used to learn A-B-C-D. Words in her dictionary are arranged in a magical order with uppercase letters having more priority over the same lowercase letters. If one such word X is a prefix of another word, Y, then X comes earlier than Y in the dictionary. then For example, all the single lettered strings will be sorted like this:
A, a, B, b, C, c and so on.
All the words in her dictionary are distinct. Your task is to ask her few queries and simulate her reply.
Input starts with an integer T (1 ≤ T ≤ 50), denoting the number of test cases.
Each case contains an integer N (4 ≤ N ≤ 50000), denoting the number of words in the dictionary.
Each of the following N lines will contain one word from her dictionary. Each word consists of lowercase and uppercase letters of the English alphabet.
It is guaranteed that the length of each word is at most 30 and starts with either of the letters 'A', 'B' , 'C' and 'D' and there is at least one word for each of these letters and all of the words are distinct.
The next line contains an integer number Q (1 ≤ Q ≤ 50000), denoting the total number of queries. The following Q lines will contain queries which will be any of the four questions as mentioned in the problem statement.
For each test case, you have to answer Q queries, if there exists more than one word for the corresponding alphabet, you have to select the one which was not answered before and which comes earlier in her dictionary. If no word matches the above criteria, then print "Already Mastered" (without quotes).
1 5 BUET DU AIUB CoU AUST 4 A for ? A for ? A for ? C for ?
AIUB AUST Already Mastered CoU
Login to submit
It's a simulation problem. You must have knowledge of following algorithms in order to solve this pr...