P10646 [NordicOI 2023] ChatNOI

翻译自 [NordicOI 2023 A 题](https://noi23.kattis.com/contests/noi23/problems/chatnoi) 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$ 个单词。

**本题采用捆绑测试**。 令 $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 100$，$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$。