Background

Translated from XXXI Olimpiada Informatyczna - Stage I CzatBBB。

Problem Description

You are given a string $S$ of length $n$ and a parameter $k$. Let $R$ be the substring formed by the last $k$ letters of $S$.

Suppose $S'$ is the new string obtained by appending one new letter to $S$.

The appending rule is as follows. For each letter $X$, count how many times it appears in $S$ immediately after an occurrence of $R$. The letter with the highest frequency is chosen as the new appended letter. If multiple letters have the highest frequency, choose the smallest one. If $R$ does not occur anywhere else in $S$, then take $X = a$. Finally, we extend $S$ by appending the letter $X$ to its end.

For example, let $S = \text{abaaabababa}$ and $k = 3$. Then the substrings where $R$ appears together with the following letter are: $\text{abaa}$, $\text{abab}$, $\text{abab}$. It most often appears with the letter $\text{b}$, so we append $\text{b}$ to $S$, obtaining $S' = \text{abaaabababab}$.

Now $S' = \text{abaaabababab}$ and $R = \text{bab}$. The substrings where $R$ appears together with the following letter are: $\text{baba}$, $\text{baba}$. Therefore, we append $a$ to the end of $S'$.

And so on. This operation will be performed infinitely many times.

Your task is to write a program that outputs the characters from position $a$ to position $b$ of the extended string.

Input Format

The first line contains four integers $n$, $k$, $a$, and $b$.

The second line contains a string of length $n$, consisting of lowercase English letters, representing the word $S$.

Output Format

Output the characters from the $a$-th to the $b$-th position of the string $S'$, i.e. the letters located at these positions in the extended word $S'$.

11 3 12 13
abaaabababa

ba

20 3 30 40
abcdabcdabcdabcdabcd

bcdabcdabcd

见附件

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

见附件

见附件

Hint

For all testdata, $2\leq n\leq10^6$, $1\leq k<n<a<b<10^{18}$, $b+1-a\leq10^6$, and the string contains only lowercase letters.

Translated by ChatGPT 5