题目描述

题目译自 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$，Mary 请你完成句子的最后 $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)$，表示在第 $i$ 个查询中应该生成多少个单词来完成句子，接下来是一个由 $k$ 个单词 $u_1, u_2, \ldots, u_k$ 组成的序列，即第 $i$ 个查询中句子的初始部分。每个单词都保证在训练文档中出现过。

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

输出格式

输出 $q$ 行，其中第 $i$ 行包含生成的单词，使得第 $i$ 个查询的完整句子具有尽可能高的质量。你只可以使用训练文档中出现的单词。如果对于给定的查询有多个可能的方案，你可以输出其中的任何一个。

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 

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

buffalo buffalo buffalo buffalo buffalo buffalo buffalo 

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 

数据范围与提示

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