Maximizing Group Quality of Constructed Strings

You are playing a conversation game with your robot. Initially, you are given a collection \(w\) of \(n\) strings (each consisting only of lowercase letters) and an integer \(k\). The quality of any string \(S\) is defined as follows:

[ Q(S) = \min_{1 \leq i \leq |S| - k} { \text{count}_w(S[i\ldots i+k]) }, ]

where \(S[i\ldots i+k]\) denotes the contiguous substring of \(S\) of length \(k+1\) starting at position \(i\) (1-indexed), and \(\text{count}_w(x)\) is the number of times the substring \(x\) appears in the set \(w\).

You will then receive \(q\) queries. Each query provides an integer \(m\) and exactly \(k\) additional strings (which you may ignore if you wish). For each query, you must construct a group of \(m\) strings so that the quality of the group is maximized. Here, the group quality is defined as the minimum quality among the \(m\) constructed strings. If there are multiple answers achieving the maximum quality, output any one of them.

Note: A constructed string must have length at least \(k+1\) so that its quality is properly defined.

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(k\) separated by a space.
2. The next \(n\) lines each contain a nonempty string, representing the set \(w\).
3. The following line contains an integer \(q\), the number of queries.
4. Each query consists of:
   1. A line containing an integer \(m\) (the number of strings to construct).
   2. Exactly \(k\) lines, each containing a string.

All strings consist only of lowercase English letters.

outputFormat

For each query, output \(m\) lines. Each line should contain one constructed string. The constructed strings should be such that the quality of the group (i.e. the minimum quality among them) is maximized. If there are multiple valid answers, output any one of them.

Recall: For a constructed string \(S\) (with \(|S| \ge k+1\)), its quality is computed as:

[ Q(S) = \min_{1 \leq i \leq |S| - k} { \text{count}_w(S[i\ldots i+k]) } ]

You do not need to output the quality value, only the constructed strings.

sample

3 1

a

aa

aaa

1

2

b

aa
aa