题目描述

Mary 对大型语言模型很感兴趣。最近聊天机器人和生成式 AI 非常流行，于是她决定设计自己的文本生成模型，叫做 ChatNOI，意思是 Chat, but Not Overly Intelligent。

模型会在一个由 $n$ 个单词组成的大文档上训练。给定训练参数 $k$，模型会统计：对于训练文档中每一种出现过的长度为 $k$ 的连续单词序列，哪些单词曾经紧跟在它后面出现过，以及各自出现了多少次。

也就是说，如果某个长度为 $k$ 的单词序列后面跟着某个单词出现了 $x$ 次，那么这个单词接在该序列后面的 似然值 为 $x$。

对于一个给定句子，Mary 会查看句子中每个长度为 $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 出现了 $1$ 次；
• and the 后面跟着 sun 出现了 $2$ 次，跟着 boat 出现了 $1$ 次；
• the sun 后面跟着 rises 出现了 $1$ 次，跟着 sets 出现了 $1$ 次。

句子 cow and the sun rises 的质量为 $1$，因为：

• cow and 后接 the 的似然值为 $1$；
• and the 后接 sun 的似然值为 $2$；
• the sun 后接 rises 的似然值为 $1$。

三者最小值为 $1$。

同理，句子 and the sun 的质量为 $2$，句子 row to the boat 的质量为 $0$。

现在，Mary 给你若干次询问。每次询问给出一个句子的前 $k$ 个单词，以及一个整数 $m$。你需要继续生成后面的 $m$ 个单词，使得完整句子的质量尽可能大。

如果有多种最优方案，输出任意一种即可。

输入格式

第一行输入两个整数 $n,k$，表示训练文档中的单词数以及训练参数。

第二行输入 $n$ 个单词 $w_1,w_2,\ldots,w_n$，表示训练文档。每个单词由 $1$ 到 $10$ 个小写英文字母组成。

第三行输入一个整数 $q$，表示询问次数。

接下来 $q$ 行，每行描述一次询问：

• 首先输入一个整数 $m_i$，表示需要生成的单词数量；
• 然后输入 $k$ 个单词 $u_1,u_2,\ldots,u_k$，表示句子的开头。

保证每个询问中的初始单词都在训练文档中出现过。

令 $M=\sum m_i$，保证 $M\le 5\cdot 10^5$。

输出格式

输出 $q$ 行。

第 $i$ 行输出第 $i$ 次询问中生成的 $m_i$ 个单词，使得完整句子的质量最大。

你只能使用训练文档中出现过的单词。若存在多种正确答案，输出任意一种。

样例 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

输出

doff
doff kikke
doff kikke lane

样例 2

输入

8 1
buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo
1
7 buffalo

输出

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

输出

you
not
heard
about
the
bird
bird
the

数据范围与计分