It is quite difficult to come up with a name for a task in Polygon (a system for preparing tasks). That is why it was necessary to automate this process by developing a name generator.
The name of any task should consist of three parts (listed in order): prefix, separator — symbol "_
" (underscore) and suffix. Examples of task names: "amazing_pascal
", "clever_einstein
", "magical_tesla
". Prefix and suffix — words consisting only of lowercase letters of the Latin alphabet, with the prefix chosen only from words in the prefix dictionary and the suffix — in the suffix dictionary.
You have been given n of words in the prefix dictionary and m of words in the suffix dictionary. You have also been given k integers qi — the numbers of titles to generate. To generate a title numbered qi, you need to find the qi-th title (numbering starts at 1), among all possible n×m titles sorted in lexicographic order.
The first line contains three integers n, m and k (1≤n,m,k≤105) — respectively the size of the prefix dictionary, the size of the suffix dictionary and the number of names to be generated.
Each of the following n lines contains the string ai (1≤∣ai∣≤16) — a word from the prefix dictionary consisting of only lowercase letters of the Latin alphabet. It is guaranteed that all words in the prefix dictionary are distinct.
Each of the following m lines contains the string bi (1≤∣bi∣≤16) — a word from the suffix dictionary consisting of only lowercase letters of the Latin alphabet. It is guaranteed that all words in the suffix dictionary are distinct.
The next line gives k integers qi (1≤qi≤n⋅m) —the numbers of names to be generated.
The entry ∣x∣ here denotes the length of the string x.
Print k lines. In the i-th line print the name of the task under the number qi.
A string s is lexicographically smaller than a string t if and only if there exists p such that si=ti for i<p and sp<tp (or p>∣s∣, p≤∣t∣).
Note: the "_
" character is lexicographically smaller than any lowercase letter.