Infinite String Extension and Substring Extraction

You are given a string \(S\) consisting of \(n\) lowercase letters and a parameter \(k\). Let \(R\) be the substring formed by the last \(k\) characters of \(S\).

We extend \(S\) by repeatedly appending a new letter according to the following rule. Suppose the current string is \(S\). To decide the new letter \(X\), for every occurrence of \(R\) in \(S\) (where \(R\) is not the suffix, so that it is immediately followed by another letter), count the letter that comes immediately after \(R\). If at least one occurrence is found, choose the letter with the highest frequency among those letters. If multiple letters tie for the highest frequency, choose the lexicographically smallest one. If \(R\) does not appear in \(S\) anywhere except as the ending substring (or not at all), then choose \(X = a\). Append \(X\) to the end of \(S\) to obtain a new string \(S'\).

This process continues indefinitely.

Your task is to output the substring (based on 1-indexing) of the infinite extended string from position \(a\) to position \(b\) (inclusive).

Note: The input consists of an initial string \(S\) on the first line, and on the second line three integers \(k\), \(a\), and \(b\), separated by spaces. It is guaranteed that \(1 \le k \le |S|\) and \(1 \le a \le b\) with \(b\) not exceeding the length up to which you need to simulate in order to output the required substring.

inputFormat

The input consists of two lines:

1. The first line contains the initial string \(S\) (a sequence of lowercase letters).
2. The second line contains three integers \(k\), \(a\), and \(b\) separated by spaces.

\(k\) denotes the number of letters used to form the substring \(R\) (from the end of \(S\)). \(a\) and \(b\) specify the starting and ending positions (1-indexed) of the substring you must output from the infinite extended string.

outputFormat

Output a single string representing the substring of the infinitely extended string from index \(a\) to index \(b\) (inclusive, 1-indexed).

sample

abaaabababa
3 3 8

aaabab