Bajtazar has discovered a passion for machine learning. He is currently working on a project for a new language model, which he has named CzatBBB (an abbreviation for Bajtocki Bot Bajtazara).
The model receives an $n$-letter word $S$ and a parameter $k$ (an integer $1 \le k < n$) as input, and then generates a continuation of this word.
Suppose we already have a word $S'$, which is an extension of $S$ by some letters. Adding a new letter works as follows (see also the example below): we consider the $k$-letter suffix $R$ of the word $S'$ and look at all previous occurrences of $R$ in $S'$ (as contiguous substrings). Then, for each letter of the alphabet, we count how many times it appeared immediately after $R$ in $S'$. Let $c$ be the letter that appeared most frequently. Ties are broken in favor of the letter that appears earlier in the alphabet, and if $R$ has not appeared anywhere else in $S'$, we set $c = \text{'a'}$. Finally, we extend the word $S'$ by appending the letter $c$ to its end.
For example, let $S = \text{abaaabababa}$ and $k = 3$. We have $S' = S$, $R = \text{aba}$, and $R$ occurs previously followed by the next letter as: $\text{abaa}$, $\text{abab}$, $\text{abab}$. The letter $\text{'b'}$ appears most frequently, so we append $\text{'b'}$ to $S'$.
Now $S' = \text{abaaabababab}$, $R = \text{bab}$, and $R$ occurs previously followed by the next letter as: $\text{baba}$, $\text{baba}$, so we append $\text{'a'}$ to $S'$.
Your task is to write a program that implements the model designed by Bajtazar.
Input
The first line of input contains four integers $n, k, a, b$ ($2 \le n \le 10^6$, $1 \le k < n$, $n < a < b < 10^{18}$, $b + 1 - a \le 10^6$). The second line of input contains an $n$-letter string consisting of lowercase English letters ('a' – 'z'), representing the word $S$.
Output
Output a string of $b + 1 - a$ characters, representing the letters in the extended word $S'$ at positions from $a$ to $b$ (inclusive). In other words, we assume that $b - n$ letters have been added to the initial word $S$, and we want to output the last $b + 1 - a$ of those added letters.
Examples
Input 1
11 3 12 13 abaaabababa
Output 1
ba
Subtasks
| Subtask | Constraints | Points |
|---|---|---|
| 1 | $n \le 100, b \le 1000$ | 8 |
| 2 | $b \le 10^8$ | 10 |
| 3 | $n \le 500$, a previous occurrence of suffix $R$ will always exist and will always be followed by the same letter | 16 |
| 4 | A previous occurrence of suffix $R$ will always exist and will always be followed by the same letter | 16 |
| 5 | $k \le 20, b \le 10^{10}$, only letters 'a' and 'b' are used | 16 |
| 6 | No additional constraints | 40 |