背景

翻译自 NordicOI 2023 A 题 ChatNOI。

题目描述

你正在和你的机器人玩一个对话游戏，规则是这样的：

首先给定一个包含了 $n$ 个字符串的仅含小写字符串组 $w$ 和一个数字 $k$。

定义一个字符串组的质量为其每个长度为 $k+1$ 的连续段的在 $w$ 中出现的次数的最小值。

有 $q$ 次询问，每次给定 $m_i$ 与 $k$ 个字符串。

你需要构造 $m_i$ 个字符串，使得在给出的 $k$ 个字符串后依次加入构造的 $m_i$ 个字符串形成的字符串组质量最大。

若有多解，只需输出任意一个。

输入格式

第一行一个整数 $n(1 \leq n \leq 5 \times 10^5)$ 和 $k (1 \leq k < n)$。

第二行一句包含 $n$ 个单词的句子 $w_i( 1\leq|w_i| \leq10)$。

第三行一个整数 $q(1 \leq q \leq 5 \times 10^5)$，表示一共有 $q$ 次询问。

然后 $q$ 行，每行一个数 $m_i$ 和长度为 $k$ 的 $s$ 的子字符串。

输出格式

你需要对于每个询问，输出 $k$ 之后的 $m_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 

提示

本题采用捆绑测试。

令 $M = \sum m_i$。

• Subtask 1（5 points）：$k < n \leq 100$，$k = 1$，$1 \leq q \leq 100$，$m_i = 1$。
• Subtask 2（7 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10^5$，$m_i = 1$。
• Subtask 3（17 points）：$k < n \leq 6$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$1 \leq m_i \leq 6$。
• Subtask 4（18 points）：$k < n \leq 5000$，$1 \leq k \leq10$，$1 \leq q \leq 5000$，$q \leq M \leq 5000$。
• Subtask 5（24 points）：$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10$，$q \leq M \leq 5 \times 10^5$。
• Subtask 6（16 points）：$k < n \leq 10^5$，$1 \leq k \leq10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。
• Subtask 7（13 points）：无特殊限制。

对于所有测试数据，$k < n \leq 5 \times 10^5$，$1 \leq k \leq 10$，$1 \leq q \leq 10^5$，$q \leq M \leq 5 \times 10^5$。