Mary 对大型语言模型的能力非常着迷。随着近期聊天机器人和生成式 AI 的热潮，她决定设计自己的文本生成模型，命名为 ChatNOI（Chat, but Not Overly Intelligent，聊天，但不算太智能）。
该模型基于一个包含 $n$ 个单词的大型文档进行训练，它将学习识别单词序列中的模式。具体来说，对于文档中出现的每一个不同的 $k$ 个连续单词序列，模型会记录在该序列之后出现的单词的频率。
例如，如果模型在以下文档上以参数 $k = 2$ 进行训练：
row row to the fishing rocks out in the ocean they go a cow is sitting and rowing and the sun rises and the sun sets but the cow and the boat are still there
它将学习到 row row 后面跟着单词 to 一次，the 后面跟着单词 sun 两次，跟着单词 boat 一次，the sun 后面跟着单词 rises 一次，跟着单词 sets 一次，依此类推。我们将某个特定 $k$ 个单词序列之后出现某个单词的频率称为该单词跟随该序列的“可能性”（likelihood）。
Mary 已经找到了如何利用训练好的模型来评估给定句子的质量。她查看句子中每一个 $k$ 个连续单词的序列，以及紧随该序列之后的单词。然后，她根据上述定义计算该单词跟随该序列的可能性。她在所有 $k$ 个连续单词序列中遇到的最小可能性即为该句子的质量。
继续上面的例子，句子 cow and the sun rises 的质量为 1，因为 cow and 后面跟着 the 的可能性为 1，the 后面跟着 sun 的可能性为 2，the sun 后面跟着 rises 的可能性为 1，其中最小值为 1。类似地，句子 and the sun 的质量为 2，句子 row to the boat 的质量为 0。
现在 Mary 已经设计好了模型和评估句子质量的方法，她向你寻求帮助，希望利用该模型来生成句子。给定句子开头的 $k$ 个单词和一个数字 $m$，Mary 请你补全该句子的最后 $m$ 个单词，使得根据训练好的模型，该句子的质量尽可能高。她对此非常兴奋，甚至可能会多次要求你执行此操作。
输入格式
输入包含： 一行，包含两个整数 $n$ 和 $k$，分别为训练文档的单词数和训练参数 $k$。 一行，包含一个由 $n$ 个单词 $w_1, w_2, \dots, w_n$ 组成的序列，即训练文档。每个单词由 1 到 10 个英文字母组成。 一行，包含一个整数 $q$，表示后续的查询次数。 $q$ 行，第 $i$ 行描述第 $i$ 个查询： 一个整数 $m_i$，其中 $1 \le m_i \le 5 \cdot 10^5$，表示为了补全第 $i$ 个查询中的句子需要生成的单词数量。 一个由 $k$ 个单词 $u_1, u_2, \dots, u_k$ 组成的序列，即第 $i$ 个查询中句子的初始部分。保证每个单词都在训练文档中出现过。
令 $M$ 为所有查询中 $m_i$ 的总和。保证 $M$ 最多为 $5 \cdot 10^5$。
输出格式
输出 $q$ 行，第 $i$ 行包含生成的单词，使得第 $i$ 个查询的完整句子具有尽可能高的质量。你只能使用训练文档中出现的单词。如果对于给定的查询有多个可能的解决方案，你可以输出其中任意一个。
子任务
| 组别 | 分值 | 数据范围 |
|---|---|---|
| 1 | 5 | $k < n \le 100, k = 1, 1 \le q \le 100, m_i = 1$ |
| 2 | 7 | $k < n \le 5 \cdot 10^5, 1 \le k \le 10, 1 \le q \le 10^5, m_i = 1$ |
| 3 | 17 | $k < n \le 6, 1 \le k \le 10, 1 \le q \le 10, 1 \le m_i \le 6$ |
| 4 | 18 | $k < n \le 5\,000, 1 \le k \le 10, 1 \le q \le 5\,000, q \le M \le 5\,000$ |
| 5 | 24 | $k < n \le 5 \cdot 10^5, 1 \le k \le 10, 1 \le q \le 10, q \le M \le 5 \cdot 10^5$ |
| 6 | 16 | $k < n \le 10^5, 1 \le k \le 10, 1 \le q \le 10^5, q \le M \le 5 \cdot 10^5$ |
| 7 | 13 | $k < n \le 5 \cdot 10^5, 1 \le k \le 10, 1 \le q \le 10^5, q \le M \le 5 \cdot 10^5$ |
样例
样例输入 1
13 2 ullen dullen doff kikke lane koff koffe lane bikke bane ullen dullen doff 3 1 ullen dullen 2 ullen dullen 3 ullen dullen
样例输出 1
doff doff kikke doff kikke lane
样例输入 2
8 1 buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo 1 7 buffalo
样例输出 2
buffalo buffalo buffalo buffalo buffalo buffalo buffalo
样例输入 3
16 1 have you not heard about the bird the bird bird bird the bird is the word 8 1 have 1 you 1 not 1 heard 1 about 1 the 1 bird 1 is
样例输出 3
you not heard about the bird bird the