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

.
/*
AizuOnline A2493
Title Replace
13/8/10 TLE
*/
#include <stdio.h>
// Select Below
//#include <stdlib.h>
#include <string.h>
//#include <float.h>
//#include <math.h>
//#include <limits.h>
//Global data section
char S[11];
int Q;
long long A,B;


struct q_st
{
        char *isextend;
        char from;
        char tostr[11];
        long long len;
        int  replace[10];
} query[300001];

int extindex;
char extend_buffer[1000][101];
//
long long calc_len(int n)
{
        int i;
        long long s;
        if(query[n].len)
                return(query[n].len);
        s=0;
        for(i=0;i<strlen(query[n].tostr);i++)
        {
                if(query[n].replace[i]==0)
                {
                        if(query[n].tostr[i]!='.')
                                s ++;
                }        
                else
                {
                        s+=calc_len(query[n].replace[i]);
                }
        }
        query[n].len=s;
#if DEBUGX
        printf("CL %d %lld\n",n,s);
#endif

        return(s);
}
void dump()
{
        int i,j;

        for(i=0;i<=Q;i++)
        {
                printf("%d:%c:",i,i==0?'-':query[i].from);
                if(query[i].isextend)
                        printf("%s",query[i].isextend);
                printf(":%lld:",query[i].len);
                printf("%s|",query[i].tostr);
                for(j=0;j<10;j++)
                        printf("%d:",query[i].replace[j]);
                printf("\n");
        }
}
char find(int num,int q)
{
        int i,runsum,runsum_old;
        static cnt=0;
#ifdef DEBUG3
        printf("FIND %d %d %d\n",num,q,cnt++);
#endif
        if(query[q].isextend)
                return(query[q].isextend[num]);

        runsum=0;runsum_old=0;
        for(i=0;i<strlen(query[q].tostr);i++)
        {
                if(!query[q].replace[i])
                {
                        if(query[q].tostr[i]!='.')
                                runsum++;
                }
                else
                        runsum+=query[query[q].replace[i]].len;
                if(!(query[q].replace[i]) && runsum_old==num)
                {
                        return(query[q].tostr[i]);
                }
                if(runsum_old <=num && runsum > num)
                {                       
                        return(find(num - runsum_old,query[q].replace[i]));
                }
                runsum_old = runsum;
        }

}
void extend(int num)
{
        int i;
        int p;

        //printf("EXT %d\n",num);

        if(extindex >= 1000)
                return;
        if(query[num].len > 100)
                return;

        query[num].isextend=extend_buffer[extindex];
        extindex++;

        for(i=0;i<strlen(query[num].tostr);i++)
                if(query[num].replace[i])
                        extend(query[num].replace[i]);

        p=0;
        
        for(i=0;i<strlen(query[num].tostr);i++)
        {
                if(query[num].replace[i]==0 && query[num].tostr[i]!='.')
                {
                        query[num].isextend[p]=query[num].tostr[i];
                        p++;
                }
                else
                {
                        strcpy(&(query[num].isextend[p]),
                               query[query[num].replace[i]].isextend);
                        p+=strlen(query[query[num].replace[i]].isextend);
                }
                
        }

}
main()
{
        int i,j,k;
        long long ret;

        scanf("%s ",&query[0].tostr[0]);
        scanf("%d %lld %lld ",&Q,&A,&B);

        for(i=1;i<=Q;i++)
        {
                scanf("%c %s ",&query[i].from,&query[i].tostr[0]);
                for(j=i-1;j>=0;j--)
                        for(k=0;k<strlen(query[j].tostr);k++)
                                if(query[i].from == query[j].tostr[k] && 
                                   !query[j].replace[k])
                                        query[j].replace[k]=i;
        }
        for(i=0;i<=Q;i++)
                query[i].isextend=NULL;
#ifdef DEBUG
        dump();
#endif
   
        ret=calc_len(0);
        extend(0);

#ifdef DEBUG
        dump();
#endif

        if(B>ret)
        {
                printf(".");
                goto END;
        }

        for(i=A-1;i<B;i++)
                printf("%c",find(i,0));
END:
     printf("\n");
return(0);
}