P10646 [NordicOI 2023] ChatNOI

Translated from [NordicOI 2023 Problem A](https://noi23.kattis.com/contests/noi23/problems/chatnoi) ChatNOI.

You are playing a dialogue game with your robot. The rules are as follows. First, you are given an array $w$ of $n$ strings (all strings contain only lowercase letters) and an integer $k$. Define the quality of an array of strings as the minimum, over every consecutive segment of length $k+1$, of the number of times that segment occurs in $w$. There are $q$ queries. In each query, you are given $m_i$ and $k$ strings. You need to construct $m_i$ strings so that, after appending these $m_i$ constructed strings one by one after the given $k$ strings, the resulting array of strings has the maximum possible quality. If there are multiple solutions, output any one of them.

The first line contains two integers $n(1 \leq n \leq 5 \times 10^5)$ and $k (1 \leq k < n)$. The second line contains a sentence of $n$ words $w_i(1 \leq |w_i| \leq 10)$. The third line contains an integer $q(1 \leq q \leq 5 \times 10^5)$, meaning there are $q$ queries in total. Then follow $q$ lines. Each line contains an integer $m_i$ and a substring of $s$ of length $k$.

For each query, you need to output the $m_i$ words after the given $k$ words.

**This problem uses bundled testdata**. Let $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 \leq 10$, $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 \leq 10$, $1 \leq q \leq 10^5$, $q \leq M \leq 5 \times 10^5$. - Subtask 7 (13 points): No special constraints. For all testdata, $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$. Translated by ChatGPT 5