Replace

Time Limit : 2 sec, Memory Limit : 262144 KB

replace

Problem Statement

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

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

最後に文字列SA文字目から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行に出力せよ.
それ以外のときは文字列SA文字目から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

.

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  komiya