replace

Problem Statement

文字列Sが与えられる． 以下の処理をQ個順番に行う．

• Sに含まれる文字c_iを全て同時に文字列p_iで置き換える．

最後に文字列SのA文字目からB文字目まで(1-indexed)を出力せよ．

Input

入力は以下の形式に従う．与えられる数は全て整数である．

S
Q A B
c_1 p_1
...
c_Q p_Q

Constraints

• 1≦Q≦3 \times 10^5
• 1≦A≦B≦10^{18}
• B-A≦10^5
• 1≦|S|≦10
• 1≦|p_i|≦10
• Sは小文字のアルファベットからなる文字列である．
• c_iは小文字のアルファベット1文字である．
• p_iは"."(ピリオド)1文字または小文字のアルファベットからなる文字列である．p_i="."(ピリオド)のとき，p_iは空文字列として扱いなさい．

Output

Q個の処理を順に行った後，Bが|S|よりも大きかったときは"."(ピリオド)を1行に出力せよ．
それ以外のときは文字列SのA文字目からB文字目まで(1-indexed)を出力せよ．

Sample Input 1

abaz
3 1 5
a cab
b .
c x

Output for the Sample Input 1

xaxaz

文字列Sは，abaz → cabbcabz → cacaz → xaxazと変化する．

Sample Input 2

original
1 2 5
x notchange

Output for the Sample Input 2

rigi

Sample Input 3

aaaa
2 1 1
a .
a nothing

Output for the Sample Input 3

.