replace replace

Problem Statement

Given the string S. The following processing is performed in the order of Q pieces.

* Replace all the characters c_i contained in S with the character string p_i at the same time.



Finally, output (1-indexed) from the A character to the B character of the character string S.

Constraints

* 1 ≤ Q ≤ 3 \ times 10 ^ 5
* 1 ≤ A ≤ B ≤ 10 ^ {18}
* B-A ≤ 10 ^ 5
* 1 ≤ | S | ≤ 10
* 1 ≤ | p_i | ≤ 10
* S is a character string consisting of lowercase alphabets.
* c_i is one lowercase alphabetic character.
* p_i is a string consisting of one "." (Period) or a lowercase alphabet. When p_i = "." (Period), treat p_i as an empty string.

Input

Input follows the following format. All given numbers are integers.


S
Q A B
c_1 p_1
...
c_Q p_Q

Output

After performing Q processes in order, if B is larger than | S |, output "." (Period) on one line.
In other cases, output (1-indexed) from the A character to the B character of the character string S.

Examples

Input

abaz
3 1 5
a cab
b .
c x


Output

xaxaz


Input

original
1 2 5
x notchange


Output

rigi


Input

aaaa
2 1 1
a .
a nothing


Output

.
using System;
using System.Text.RegularExpressions;

namespace Replace {
	class Program {
		static void Main(string[] args) {

			string S = Console.ReadLine();
			string[] str = Console.ReadLine().Split(' ');
			int Q = int.Parse(str[0]);
			int A = int.Parse(str[1]);
			int B = int.Parse(str[2]);
			string[] from_list = new string[Q];
			string[] to_list = new string[Q];
			for (int i = 0; i < Q; i++) {
				str = Console.ReadLine().Split(' ');
				from_list[i] = str[0];
				to_list[i] = str[1] == "." ? "" : str[1];
			}
			for (int i = 0; i < Q; i++) {
				S = Regex.Replace(S, from_list[i], to_list[i]);
			}

			if (S.Length > B) {
				S = ".";
			}
			else {
				if (S.Length != B) S.Remove(B);
				if (S.Length != 1) S.Remove(0, A - 1);
			}
			Console.WriteLine(S);
		}
	}
}