chatnoi (NOINordic contest)
Time limit: 4 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: string, graph theory, binary search, dynamic programming

\problemname{ChatNOI}
Mary is fascinated by the power of large language models. With all the recent
hype around chat bots and generative AI, she decided to design her own text
generation model called ChatNOI (Chat, but Not Overly Intelligent).

The model is trained on a large document consisting of $n$ words, where it will
learn to recognise patterns in sequences of words. Specifically, for every
distinct sequence of $k$ consecutive words appearing in the document, the model
will keep track of the frequency of words that occur as the next word following
this sequence of $k$ words.

As an example, if the model is trained with the parameter $k = 2$ on the document
\begin{center}
\begin{verbatim}
row row to the fishing rocks
out in the ocean they go
a cow is sitting and rowing
and the sun rises
and the sun sets
but the cow and the boat are still there
\end{verbatim}
\end{center}
it will learn that \texttt{row row} is followed once by the word \texttt{to},
\texttt{and the} is followed twice by the word \texttt{sun} and once by the
word \texttt{boat}, \texttt{the sun} is followed once by the word
\texttt{rises} and once by the word \texttt{sets}, and so on. We call the
frequency of a word following a particular sequence of $k$ words the
\textit{likelihood} of that word following that sequence.

Mary has figured out how she can use a trained model to rank the quality of a
given sentence. She looks at every sequence of $k$ consecutive words in the
sentence, and the word that follows that sequence. She then calculates the
likelihood of that word following that sequence, as per the above
definition. The minimum likeliness that she encounters out of all $k$
consecutive words is the quality of that sentence.

Continuing with the above example, the sentence \texttt{cow and the sun rises}
has a quality of $1$, because \texttt{cow and} is followed by \texttt{the} with
a likelihood of $1$, \texttt{and the} is followed by \texttt{sun} with a
likelihood of $2$, and \texttt{the sun} is followed by \texttt{rises} with a
likelihood of $1$, the minimum of which is $1$. Similarly the sentence
\texttt{and the sun} has a quality of $2$ and the sentence \texttt{row to the
boat} has a quality of $0$.

Now that Mary has designed the model and a way to \textit{rank} the quality of
a given sentence, she turns to you for help in using the model to
\textit{generate} sentences. Given the first $k$ words in a sentence and a
number $m$, Mary asks you to finish the last $m$ words of that sentence so that
it has the maximum quality possible according to the trained model. She is
pretty excited so she may even ask you to do this multiple times.

\section*{Input}
The input consists of:
\begin{itemize}
  \item One line with two integers $n$ and $k$, the number of words in the training document and the training
        parameter $k$ as described above.
  \item One line with a sequence of $n$ words $w_1, w_2, \ldots, w_n$, the training document.
        Each word consists of $1$ to $10$ lowercase characters from the English alphabet.
  \item One line with an integer $q$, the number of queries to follow.
  \item $q$ lines, the $i$th of which describes the $i$th query:
    \begin{itemize}
      \item An integer $m_i$, where $1 \leq m_i \leq 5 \cdot 10^5$, the number of words that
            should be generated to complete the sentence in the $i$th query, and
      \item a sequence of $k$ words $u_1, u_2, \ldots, u_k$, the initial part of
            the sentence in the $i$th query.
            Each word is guaranteed to have appeared in the training document.
    \end{itemize}
\end{itemize}

Let $M$ denote the sum of $m_i$ over all queries $i$. It is guaranteed that $M$
is at most $5 \cdot 10^5$.

\section*{Output}
Output $q$ lines, the $i$th line containing the generated words so that the
complete sentence for the $i$th query has the maximum quality possible. You may
only use words that appear in the training document. If there are multiple
possible solutions for a given query then you may output any one of them.

\section*{Scoring}
\begin{tabular}{|l|l|l|}
    \hline
    Group & Points & Constraints \\ \hline
    1     & 5      & $k < n \leq 100$,           $k = 1$,            $1 \leq q \leq 100$,  $m_i = 1$ \\ \hline % frequency table lookup: O(n*k + q*k)
    2     & 7      & $k < n \leq 5 \cdot 10^5$,  $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $m_i = 1$ \\ \hline % frequency table lookup: O(n*k + q*k)
    3     & 17     & $k < n \leq 6$,             $1 \leq k \leq 10$, $1 \leq q \leq 10$,   $1 \leq m_i \leq 6$  \\ \hline %
    4     & 18     & $k < n \leq 5\,000$,        $1 \leq k \leq 10$, $1 \leq q \leq 5\,000$, $q \leq M \leq 5\,000$ \\ \hline % DP(vertex, path length): O(n*k + n*M)
    5     & 24     & $k < n \leq 5 \cdot 10^5$,  $1 \leq k \leq 10$, $1 \leq q \leq 10$,   $q \leq M \leq 5 \cdot 10^5$ \\ \hline % Binary search + SCC + DP longest path: O(n*k + q * log(n) + M)
    6     & 16     & $k < n \leq 10^5$,          $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $q \leq M \leq 5 \cdot 10^5$ \\ \hline % SCC + DP longest path for each distinct edge weight: O(n*k + n*sqrt(n) + M)
    7     & 13     & $k < n \leq 5 \cdot 10^5$,  $1 \leq k \leq 10$, $1 \leq q \leq 10^5$, $q \leq M \leq 5 \cdot 10^5$ \\ \hline % Clever observation: O(n*k + n*log(n) + M)
\end{tabular}



Starter code:

Grader code:

Setup script:

Evaluation script: