cho.sh

Endless String

Starting from a string A, repeatedly replace every $ in S with the previous result, then print characters from position min to max after N runs.

Medium4StringRecursionBinary searchMathNo attempts yetTime limit2sMemory limit128 MB

Problem

An initial string A is given. Each time the program runs, it creates a new string using a fixed string S. The string S consists of lowercase English letters and the symbol $; every $ in S is replaced with the input string from that run. The resulting string is the output of that run and becomes the input for the next run.

Given the initial string, the string S, and the number of runs N, print the characters from position min through position max in the string produced after N runs.

Input

The first line contains the initial string A. It consists only of lowercase English letters, and its length is at most 50.

The second line contains the string S. Its length is between 2 and 50 inclusive, and its first character is always $. The string S consists only of lowercase English letters and $.

The third line contains the number of runs N. N is an integer from 1 to 1,000,000,000 inclusive.

The fourth line contains min and max. min is an integer from 1 to 1,000,000,000 inclusive, and max is at least min and at most min + 99.

Output

Print one line containing the characters from position min through position max in the string after N runs. If a position does not exist in the string, print - for that position.