Problem Background

Translated from NordicOI 2023 A Problem ChatNOI.

Problem Description

You are playing a dialogue game with your robot, with the following rules:

Initially, you are given a set \( w \) containing \( n \) strings consisting only of lowercase characters and a number \( k \).

The quality of a segment is defined as the minimum count of each consecutive segment of length \( k+1 \) that appears in \( w \).

There are \( q \) queries. Each query provides \( m_i \) and \( k \) strings. You need to construct \( m_i \) strings such that the quality of the string set is maximized, and you only need to 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 with \( 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 \)), indicating the total number of queries.

Then \( q \) lines follow, each containing a number \( m_i \) and a substring of length \( k \) from \( s \).

Output Format

For each query, you need to output the \( m_i \) words following the \( k \) words.

Sample Input and Output

Sample Input #1

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

Sample Output #1

doff 
doff kikke 
doff kikke lane 

Sample Input #2

8 1
buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo
1
7 buffalo

Sample Output #2

buffalo buffalo buffalo buffalo buffalo buffalo buffalo 

Sample Input #3

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

Sample Output #3

you 
not 
heard 
about 
the 
bird 
bird 
the 

Notes

This problem uses batched testing.

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 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 \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 restrictions.

For all test data, \( 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 \).

见题面 Input 部分

见题面 Output 部分