Problem Description

Given a string \( S \) of \( n \) letters and a parameter \( k \), let \( R \) be the substring formed by the last \( k \) letters of \( S \).

Suppose the string \( S' \) is generated by adding a new letter to \( S \).

The rules for adding a letter are as follows: For a letter \( X \), calculate the number of times it appears immediately after \( R \) in the string \( S \). The letter with the highest frequency is chosen as the new letter to be added. If there are multiple letters with the highest frequency, the smallest one is chosen. If \( R \) does not appear elsewhere in the string \( S \), then \( X = a \). Finally, we extend the string \( S \) by appending the letter \( X \) to its end.

For example, let \( S = \text{abaaabababa} \) and \( k = 3 \), then the substrings formed by \( R \) and the next letter are: \( \text{abaa} \), \( \text{abab} \), \( \text{abab} \). It most frequently appears with the letter \( \text{b} \), so we add \( \text{b} \) to \( S \), resulting in \( S' = \text{abaaabababab} \).

Now, \( S' = \text{abaaabababab} \), \( R = \text{bab} \), the substrings formed by \( R \) and the next letter are: \( \text{baba} \), \( \text{baba} \). Thus, we append \( a \) to \( S' \).

This process continues indefinitely.

Your task is to write a program that outputs the last \( a \) to \( b \) characters of the new string.

Input Format

The first line of input contains four integers \( n \), \( k \), \( a \), and \( b \).

The second line of input contains a string of \( n \) lowercase English letters, representing the word \( S \).

Output Format

Output the \( a \)-th to \( b \)-th characters of the string \( S' \), representing the letters in the extended word \( S' \) at the specified positions.

Sample Input and Output

Sample Input #1

11 3 12 13
abaaabababa

Sample Output #1

ba

Sample Input #2

20 3 30 40
abcdabcdabcdabcdabcd

Sample Output #2

bcdabcdabcd

Sample Input #3

(Not provided)

Sample Output #3

(Not provided)

Sample Input #4

(Not provided)

Sample Output #4

(Not provided)

Notes/Hints

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

见题面 Input 部分

见题面 Output 部分