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 id[128][300010];
int num[128] = {};
void chg(char c, string s) {
  if (s == ".") {
    NODE *u = &id[c][num[c]];
    u->var = '.';
    num[c]++;
  } else {
    NODE *u = &id[c][num[c]];
    u->var = '.';
    num[c]++;
    for (int i = 0; i < s.size(); i++) {
      u->ch.push_back(&id[s[i]][num[s[i]]]);
    }
  }
}
map<NODE *, long long> memo;
long long cnt(NODE *r) {
  if (memo.count(r)) return memo[r];
  if (r->ch.size() == 0) {
    return r->var == '.' ? 0 : 1;
  } else {
    long long res = 0;
    for (int i = 0; i < r->ch.size(); i++)
      res = min((2000000000000000000ll), res + cnt(r->ch[i]));
    return memo[r] = res;
  }
}
long long A, B;
string res;
void func(NODE *r, long long now) {
  if (now + cnt(r) <= A) return;
  if (now >= B) return;
  if (r->ch.size() == 0) {
    if (r->var != '.') {
      res += r->var;
    }
    return;
  } else {
    for (int i = 0; i < r->ch.size(); i++) {
      func(r->ch[i], now);
      now += cnt(r->ch[i]);
    }
  }
}
int main() {
  string S;
  cin >> S;
  NODE *root = &id['.'][0];
  for (int i = 0; i < 128; i++)
    for (int j = 0; j < 300010; j++) id[i][j].var = i;
  chg('.', S);
  int Q;
  cin >> Q >> A >> B;
  while (Q--) {
    char c;
    string p;
    cin >> c >> p;
    chg(c, p);
  }
  --A;
  if (cnt(root) < B) {
    cout << "." << endl;
  } else {
    func(root, 0);
    cout << res << endl;
  }
}
