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;
const long long INF = LLONG_MAX / 4;
int q;
vector<string> s(1);
vector<vector<int> > to;
vector<long long> len;
void solve(long long a, long long b) {
  stack<pair<int, int> > stk;
  stk.push(make_pair(0, 0));
  for (;;) {
    int i = stk.top().first;
    int j = stk.top().second;
    stk.pop();
    while (j < (int)s[i].size()) {
      int next = to[i][s[i][j] - 'a'];
      if (next == -1) {
        if (a <= 0) cout << s[i][j];
        --a;
        --b;
      } else {
        if (a < len[next]) {
          stk.push(make_pair(i, j + 1));
          stk.push(make_pair(next, 0));
          break;
        } else {
          a -= len[next];
          b -= len[next];
        }
      }
      if (b < 0) {
        cout << endl;
        return;
      }
      ++j;
    }
  }
}
int main() {
  long long a, b;
  cin >> s[0] >> q >> a >> b;
  ++q;
  s.resize(q);
  vector<char> c(q);
  for (int i = 1; i < q; ++i) {
    cin >> c[i] >> s[i];
    if (s[i] == ".") s[i] = "";
  }
  to.assign(q, vector<int>(26, -1));
  len.resize(q, 0);
  for (int i = q - 1; i >= 0; --i) {
    int n = s[i].size();
    for (int j = 0; j < n; ++j) {
      int next = to[i][s[i][j] - 'a'];
      if (next == -1)
        ++len[i];
      else
        len[i] += len[next];
      len[i] = min(len[i], INF);
    }
    if (i > 0) {
      to[i - 1] = to[i];
      if (s[i].size() == 1 && to[i][s[i][0] - 'a'] != -1)
        to[i - 1][c[i] - 'a'] = to[i][s[i][0] - 'a'];
      else
        to[i - 1][c[i] - 'a'] = i;
    }
  }
  if (b > len[0])
    cout << "." << endl;
  else
    solve(a - 1, b - 1);
  return 0;
}
