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>
using namespace std;
string S;
long long Q, A, B;
struct NODE {
  char c;
  vector<NODE *> ch;
};
NODE *alp[128] = {};
map<NODE *, long long> memo;
long long add(long long a, long long b) {
  return (long double)a + b >= (1e18 + 10000) ? (1e18 + 10000) : a + b;
}
long long size(NODE *r) {
  if (r->c != '.') return 1;
  if (memo.count(r)) return memo[r];
  memo[r] = 0;
  for (int i = 0; i < r->ch.size(); i++) {
    memo[r] = add(memo[r], size(r->ch[i]));
  }
  return memo[r];
}
int C = 0;
int F = 0;
int dfs(NODE *r, long long cur) {
  if (C == 0 && F == 1) return 0;
  if (r->c != '.') {
    if (cur == 0 && F == 0) {
      F = 1;
      cout << r->c;
      C = B - A;
    } else if (F) {
      if (C > 0) {
        C--;
        cout << r->c;
      }
    }
  }
  for (int i = 0; i < r->ch.size(); i++) {
    if (F) {
      dfs(r->ch[i], cur);
    } else {
      if (size(r->ch[i]) <= cur) {
        cur -= size(r->ch[i]);
      } else {
        dfs(r->ch[i], cur);
      }
    }
  }
}
int main() {
  for (int i = 'a'; i <= 'z'; i++) {
    alp[i] = new NODE();
    alp[i]->c = i;
  }
  NODE *root = new NODE();
  root->c = '.';
  cin >> S;
  for (int i = 0; i < S.size(); i++) {
    root->ch.push_back(alp[S[i]]);
  }
  cin >> Q >> A >> B;
  A--, B--;
  for (int i = 0; i < Q; i++) {
    char x;
    string y;
    cin >> x >> y;
    NODE *prev = alp[x];
    prev->c = '.';
    alp[x] = new NODE();
    alp[x]->c = x;
    if (y != ".") {
      for (int j = 0; j < y.size(); j++) {
        prev->ch.push_back(alp[y[j]]);
      }
    }
  }
  if (size(root) <= B) {
    cout << "." << endl;
    return 0;
  }
  dfs(root, A);
  cout << endl;
}
