Making ChatGPT

Jiwon is a graduate student in the AI graduate school at GIST, and in principle should be able to build a home ChatGPT-style model without much trouble. But Jiwon is lazy, so instead of a deep learning language model, Jiwon will use a slightly modified n-gram model, a basic NLP technique.

Given a single character, Jiwon's language model predicts the next character by looking at the training corpus. The training corpus consists of several strings. When a character $c$ is given, the model searches the training corpus for every occurrence of $c$, then finds the character $c'$ that appears most often immediately after $c$, and predicts that the next character after $c$ is $c'$. Note that $c=c'$ is possible. If several characters tie for the most frequent, the model chooses the one with the smallest ASCII code. If the character $c$ does not appear in the training corpus, the model cannot predict the next character and an error occurs.

The training corpus uses only the character [ marking the start of a sentence, the character ] marking the end of a sentence, the lowercase letters a to z, and the character -, which replaces spaces. Every sentence in the corpus starts with [, ends with ], and has length at least $3$. The character [ appears only at the start of a sentence, and the character ] appears only at the end of a sentence.

To generate a sentence with the model, first input the start character [. When the model predicts the next character $c_1$, append it to the sentence being generated. Then input $c_1$ into the model to predict the next character $c_2$, and repeat. If the end character ] appears during this process, stop generating. Otherwise, the prediction keeps going forever. You can prove that as long as the training corpus is not empty, the model never reaches a state where it cannot predict the next character.

Given the training corpus, guess a substring of the string that this model generates, together with Jiwon.

The first line contains three integers $N$, $K$, and $M$, separated by spaces. The training corpus consists of $N$ sentences, and the program must output the characters from the $K$-th to the $(K+M-1)$-th of the string generated by the language model trained on this corpus. ($1 \leq N \leq 100\,000$, $1 \leq K \leq 10^{18}$, $1 \leq M \leq 1\,000$)

From the second line onward, the $N$ lines each contain one sentence of the training corpus as a string. Each line starts with [ and ends with ], and has length at least $3$. The character [ appears only at the start of each line, and the character ] appears only at the end of each line.

The total length of all strings in the training corpus does not exceed $300\,000$.

Output the characters from the $K$-th to the $(K+M-1)$-th of the string generated by the language model trained on the given corpus. When printing the $i$-th character, if the generated string is too short and has no $i$-th character, print . instead.

The ASCII code of - is 45, the ASCII code of [ is 91, the ASCII code of ] is 93, and the ASCII code of a is 97.