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$ 个字符串，使得这个字符串组质量最大，只需输出任意一个。

无

无

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