Name generator#11539
Coming up with a name for a task in Polygon (a system for preparing programming problems) can be quite difficult. Therefore, it was decided to automate this process by developing a task name generator.
Every task name must consist of three parts (in order): a prefix, a separator (the character "_" — an underscore), and a suffix. For example: "amazing_pascal", "clever_einstein", "magical_tesla". Both the prefix and the suffix are words consisting only of lowercase Latin letters. The prefix is chosen from the prefix dictionary, and the suffix is chosen from the suffix dictionary.
You are given words from the prefix dictionary and words from the suffix dictionary. You are also given integers, q_i, representing the indices of the names to generate. To generate the name with index q_i, find the q_i-th name (numbering starts from ) in the list of all possible n \times m names (each formed as "prefix_suffix"), sorted in lexicographical order.
The first line contains three integers: , , and (1 \le n, m, k \le 10^5) — the number of prefixes, the number of suffixes, and the number of names to generate, respectively.
The next lines each contain a string a_i (1 \le |a_i| \le 16) — a word from the prefix dictionary, consisting only of lowercase Latin letters. All words in the prefix dictionary are guaranteed to be distinct.
The following lines each contain a string b_i (1 \le |b_i| \le 16) — a word from the suffix dictionary, consisting only of lowercase Latin letters. All words in the suffix dictionary are guaranteed to be distinct.
The next line contains integers q_i (1 \le q_i \le n \cdot m) — the required indices of names to be generated.
The notation denotes the length of string .
Print lines. The -th line should contain the task name with index q_i.
A string is lexicographically smaller than a string if and only if there exists such that s_i = t_i for all i < p and s_p < t_p (or p > |s|, p \le |t|).
Note: The "_" character is lexicographically smaller than any lowercase Latin letter.
Example 1