String Decompression

Interview

Time limit1sMemory limit1024 MB

Summary

Given patterns mapped to uppercase letters and a compressed string, expand it and print characters S through E of the original string.

Level: Medium6 of 10
Topics: String, Implementation, Recursion, Simulation
Solved: No attempts yet

Problem

There is a program called SPC (String Pattern Compressor) that compresses a specific lowercase string pattern into a single uppercase letter.

For example, when compression is done as follows, “ $\text{aabbaaac}$ ” is compressed into “ $\text{ABAC}$ ”.


lowercase string pattern	uppercase
$\text{aa}$	$\text{A}$
$\text{bba}$	$\text{B}$
$\text{c}$	$\text{C}$

Given a compression program and a compressed string, write a program that outputs part of the string before compression.

Input

The first line gives the number of compression methods $N$ . ( $1 \le N \le 26$ )

From the second line, $N$ lines follow, each containing a lowercase string pattern and the corresponding uppercase letter, separated by a space. The length of each lowercase string pattern does not exceed $1\,000$ , and the same uppercase letter is not given more than once.

The $N+1$ -th line gives the compressed string. The length of the compressed string does not exceed $1\,000$ .

The last line gives two integers $S$ and $E$ . ( $1 \le S \le E \le$ (length of the string before compression))

Output

Output the $S$ -th character through the $E$ -th character of the string before compression.

Examples3

Example 1
Input
```
3
aa A
bba B
c C
ABAC
4 6
```
Expected output
```
baa
```

Example 2

Input

5
abcde A
abcde B
abcde C
abcde D
abcde E
ABCDE
1 25

Expected output

abcdeabcdeabcdeabcdeabcde

Example 3
Input
```
4
e E
f F
g G
h H
EEEFEEE
4 5
```
Expected output
```
fe
```