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;
struct NODE {
  char var;
  vector<NODE *> ch;
};
NODE *nowTarget[128];
NODE id[400000 * 10];
int pool = 0;
NODE *next(char c) {
  id[pool].var = c;
  return &id[pool++];
}
void chg(char c, string s) {
  if (s == ".") {
    NODE *u = nowTarget[c];
    u->var = '.';
    nowTarget[c] = next(c);
  } else {
    NODE *u = nowTarget[c];
    u->var = '.';
    nowTarget[c] = next(c);
    for (int i = 0; i < s.size(); i++) {
      u->ch.push_back(nowTarget[s[i]]);
    }
  }
}
map<NODE *, long long> memo;
long long cnt(NODE *r) { return memo[r]; }
long long cnt2(NODE *r) {
  stack<NODE *> S;
  S.push(r);
  vector<NODE *> v;
  while (S.size()) {
    v.push_back(r);
    r = S.top();
    S.pop();
    if (r->ch.size() == 0) {
      if (r->var != '.') {
        memo[r] = 1;
      } else {
        memo[r] = 0;
      }
    } else {
      for (int i = 0; i < r->ch.size(); i++) {
        S.push(r->ch[i]);
      }
    }
  }
  long long res = 0;
  reverse(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++) {
    r = v[i];
    if (memo.count(r)) continue;
    long long now = 0;
    for (int i = 0; i < r->ch.size(); i++) {
      now = min((2000000000000000000ll), now + cnt(r->ch[i]));
    }
    memo[r] = now;
  }
}
long long A, B;
char res[100010];
void func(NODE *r, long long now) {
  stack<pair<NODE *, long long> > S;
  S.push({r, now});
  while (S.size()) {
    r = S.top().first;
    now = S.top().second;
    S.pop();
    if (now + cnt(r) <= A) continue;
    if (now >= B) continue;
    ;
    if (r->ch.size() == 0) {
      if (r->var != '.') {
        res[now - A] = r->var;
      }
      continue;
    } else {
      for (int i = 0; i < r->ch.size(); i++) {
        S.push({r->ch[i], now});
        now = min((2000000000000000000ll), now + cnt(r->ch[i]));
      }
    }
  }
}
int main() {
  string S;
  cin >> S;
  for (int i = 0; i < 128; i++) nowTarget[i] = next(i);
  NODE *root = nowTarget['.'];
  chg('.', S);
  int Q;
  cin >> Q >> A >> B;
  while (Q--) {
    char c;
    string p;
    cin >> c >> p;
    chg(c, p);
  }
  cnt2(root);
  --A;
  if (cnt(root) < B) {
    cout << "." << endl;
  } else {
    func(root, 0);
    cout << res << endl;
  }
}
