Background

Translated from NordicOI 2023 Problem A ChatNOI.

Problem Description

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.

Input Format

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$.

Output Format

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

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 

Hint

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