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

.
#include <bits/stdc++.h>
char S[11];
int Q;
long long A, B;
struct q_st {
  char from;
  char tostr[11];
  long long len;
  int replace[10];
} query[300001];
long long calc_len(int n) {
  int i;
  long long s;
  s = 0;
  for (i = 0; i < strlen(query[n].tostr); i++) {
    if (query[n].replace[i] == 0)
      s++;
    else {
      s += calc_len(query[n].replace[i]);
    }
  }
  query[n].len = s;
  return (s);
}
void dump() {
  int i, j;
  for (i = 0; i <= Q; i++) {
    printf("%d:%c:", i, i == 0 ? '-' : query[i].from);
    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;
  runsum = 0;
  runsum_old = 0;
  for (i = 0; i < strlen(query[q].tostr); i++) {
    if (!query[q].replace[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;
  }
}
int 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;
  }
  ret = calc_len(0);
  if (B > ret)
    printf("-1");
  else
    for (i = A - 1; i <= B - 1; i++) printf("%c", find(i, 0));
  printf("\n");
  return (0);
}
