Problem: 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

.

Solution (in CPP):

Solution:
#include<stack>
#include<cstdio>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const ll INF=1LL<<61;

const int Q_MAX=300000;

int q;
ll a,b;

char from[Q_MAX+1],to[Q_MAX+1][16];

// dp[c][dep] := ( 文字 c からはじめて, クエリ dep, dep+1, ..., q-1 を順に処理したときにできる文字列の長さ )
ll dp[26][Q_MAX];
ll dfs_count(char c,int dep){
	if(dep==q) return 1;

	ll &res=dp[c-'a'][dep];
	if(res!=-1) return res;

	if(from[dep]==c){
		res=0;
		for(int i=0;to[dep][i];i++){
			res+=dfs_count(to[dep][i],dep+1);
			res=min(res,INF);
		}
	}
	else{
		res=dfs_count(c,dep+1);
	}
	return res;
}

struct state{
	int pos;
	char c;
	int dep;
};

int main(){
	char s[16];
	scanf("%s%d%lld%lld",s,&q,&a,&b);
	a--;
	rep(i,q){
		scanf(" %c%s",from+i,to[i]);
		if(to[i][0]=='.') to[i][0]='\0';
	}

	memset(dp,-1,sizeof dp);
	// 再帰が深くならないように適当に間引いて計算しておく
	for(char c='a';c<='z';c++) for(int dep=q-1;dep>=0;dep-=100) dfs_count(c,dep);

	// 経路圧縮用
	static char next_c[26][Q_MAX+1];
	static int next_dep[26][Q_MAX+1];
	// next_c, next_dep を初期化
	for(char c='a';c<='z';c++) rep(dep,q+1) {
		char &c2=next_c[c-'a'][dep];
		int &dep2=next_dep[c-'a'][dep];
		if(dep==q){
			c2=c;
			dep2=dep;
		}
		else{
			if(from[dep]==c){
				int len=strlen(to[dep]);
				int cnt=0,i0=-1;
				rep(i,len) if(dfs_count(to[dep][i],dep+1)>0) cnt++, i0=i;

				if(cnt!=1){
					c2=c;
					dep2=dep;
				}
				else{
					c2=to[dep][i0];
					dep2=dep+1;
				}
			}
			else{
				c2=c;
				dep2=dep+1;
			}
		}
	}

	int sz=0;
	static char ans[100010];

	ll cnt=0;
	stack<state> S;
	for(int i=strlen(s)-1;i>=0;i--){
		S.push((state){0,s[i],0});
	}
	while(!S.empty()){
		int pos=S.top().pos;
		char c=S.top().c;
		int dep=S.top().dep; S.pop();

		if(pos==0){
			if(sz==b-a) continue;

			if(a<=cnt && dep==q) ans[sz++]=c;

			ll num=dfs_count(c,dep);
			if(cnt+num<=a){
				cnt+=num;
			}
			else{
				char c2=next_c[c-'a'][dep];
				int dep2=next_dep[c-'a'][dep];
				// 経路圧縮しない
				if(dep2==dep){
					int len=strlen(to[dep]);
					for(int i=len-1;i>=0;i--) if(dfs_count(to[dep][i],dep+1)>0) S.push((state){0,to[dep][i],dep+1});
				}
				// 経路圧縮する
				else{
					S.push((state){1,c,dep});
					S.push((state){0,c2,dep2});
				}
			}
		}
		else{ // pos==1
			char c2=next_c[c-'a'][dep];
			int dep2=next_dep[c-'a'][dep];
			next_c[c-'a'][dep]=next_c[c2-'a'][dep2];
			next_dep[c-'a'][dep]=next_dep[c2-'a'][dep2];
		}
	}

	if(sz<b-a) puts(".");
	else       puts(ans);

	return 0;
}