Bessie’s miV Find‐and‐Replace

Bessie is playing with the state‐of‐the‐art text editor miV. Its powerful find‐and‐replace feature lets her take any lowercase English letter \(c\) and replace every occurrence of that letter with a nonempty string \(s\) of lowercase letters. For example, if she starts with the string ball and chooses \(c=l\) and \(s=na\), then all occurrences of l are replaced to obtain banana.

Bessie begins with the string a and performs a sequence of such find‐and‐replace operations. After all operations the final string is \(S\). Since \(S\) can be enormous, she only wants to know a small part of it. Given two integers \(l\) and \(r\) with \(1 \le l \le r \le \min(|S|,10^{18})\), determine the substring \(S_{l\cdots r}\) (i.e. the characters from the \(l\)–th to the \(r\)–th, inclusive).

It is guaranteed that the sum of \(|s|\) over all operations is at most \(2\cdot10^5\), and that \(r-l+1\le 2\cdot 10^5\).

Note: If a letter \(c\) is replaced by the string \(s\), then in the final string \(S\) every occurrence of \(c\) in the current string is replaced simultaneously by \(s\). Operations are applied in the given order.

inputFormat

The first line contains a single integer \(n\) (the number of operations).

Each of the next \(n\) lines contains a lowercase letter and a nonempty string of lowercase letters separated by a space. This indicates that in one operation, Bessie replaces every occurrence of the specified letter with the given string.

The last line contains two integers \(l\) and \(r\) (with \(1 \le l \le r \le \min(|S|,10^{18})\) and \(r-l+1 \le 2\cdot10^5\)), which specify that you should output \(S_{l\cdots r}\), the substring of \(S\) from the \(l\)–th to the \(r\)–th character.

outputFormat

Output the substring \(S_{l\cdots r}\) of the final string \(S\) after applying all the operations.

sample

1
a ball
2 4

all