题目描述
题目译自 NordicOI 2023 T1 「ChatNOI」

Mary 对大型语言模型的能力感到着迷。随着聊天机器人和生成式 AI 的最新热潮，她决定设计自己的文本生成模型，称为 ChatNOI（Chat，但不太智能）。

该模型在由 $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
• and the 后面跟两次单词 sun 和跟一次单词 boat
• the sun 后面跟一次单词 rises 和跟一次单词 sets

我们称紧随特定序列的单词的频率为该单词的可能性。

---

句子质量评估

Mary 提出了句子质量的评估方法：她查看句子中的每个 $k$ 个连续单词序列及其后面的单词，计算该单词紧随该序列的可能性。所有 $k$ 个连续单词序列中的最小可能性就是该句子的质量。

继续上面的例子：

• 句子 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$，分别表示训练文档中的单词数和训练参数 $k$。

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

第三行包含一个整数 $q$，表示查询数量。

接下来 $q$ 行，第 $i$ 行描述第 $i$ 个查询：

• 首先有一个整数 $m_i$ $(1 \leq m_i \leq 5 \cdot 10^5)$，表示应该生成多少个单词来完成句子
• 然后是由 $k$ 个单词 $u_1, u_2, \ldots, u_k$ 组成的序列，即句子的初始部分

每个单词都保证在训练文档中出现过。

令 $M$ 表示所有查询中 $m_i$ 的总和。保证 $M$ 最多为 $5 \cdot 10^5$。

---

输出格式

输出 $q$ 行，其中第 $i$ 行包含生成的单词，使得第 $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 

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	5	$k < n \leq 100$, $k = 1$, $1 \leq q \leq 100$, $m_i = 1$
2	7	$k < n \leq 5 \cdot 10^5$, $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $m_i = 1$
3	17	$k < n \leq 6$, $1 \leq k \leq 10$, $1 \leq q \leq 10$, $1 \leq m_i \leq 6$
4	18	$k < n \leq 5\,000$, $1 \leq k \leq 10$, $1 \leq q \leq 5\,000$, $q \leq M \leq 5\,000$
5	24	$k < n \leq 5 \cdot 10^5$, $1 \leq k \leq 10$, $1 \leq q \leq 10$, $q \leq M \leq 5 \cdot 10^5$
6	16	$k < n \leq 10^5$, $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $q \leq M \leq 5 \cdot 10^5$
7	13	$k < n \leq 5 \cdot 10^5$, $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $q \leq M \leq 5 \cdot 10^5$