All of us know that girls in Arpa’s land are... ok, you’ve got the idea :D

Anyone knows that Arpa isn't a normal man, he is ... well, sorry, I can't explain it more. Mehrdad is interested about the reason, so he asked Sipa, one of the best biology scientists in Arpa's land, for help. Sipa has a DNA editor.

<image>

Sipa put Arpa under the DNA editor. DNA editor showed Arpa's DNA as a string S consisting of n lowercase English letters. Also Sipa has another DNA T consisting of lowercase English letters that belongs to a normal man.

Now there are (n + 1) options to change Arpa's DNA, numbered from 0 to n. i-th of them is to put T between i-th and (i + 1)-th characters of S (0 ≤ i ≤ n). If i = 0, T will be put before S, and if i = n, it will be put after S.

Mehrdad wants to choose the most interesting option for Arpa's DNA among these n + 1 options. DNA A is more interesting than B if A is lexicographically smaller than B. Mehrdad asked Sipa q questions: 

Given integers l, r, k, x, y, what is the most interesting option if we only consider such options i that l ≤ i ≤ r and <image>? If there are several most interesting options, Mehrdad wants to know one with the smallest number i.

Since Sipa is a biology scientist but not a programmer, you should help him.

Input

The first line contains strings S, T and integer q (1 ≤ |S|, |T|, q ≤ 105) — Arpa's DNA, the DNA of a normal man, and the number of Mehrdad's questions. The strings S and T consist only of small English letters.

Next q lines describe the Mehrdad's questions. Each of these lines contain five integers l, r, k, x, y (0 ≤ l ≤ r ≤ n, 1 ≤ k ≤ n, 0 ≤ x ≤ y < k).

Output

Print q integers. The j-th of them should be the number i of the most interesting option among those that satisfy the conditions of the j-th question. If there is no option i satisfying the conditions in some question, print -1.

Examples

Input

abc d 4
0 3 2 0 0
0 3 1 0 0
1 2 1 0 0
0 1 3 2 2


Output

2 3 2 -1 


Input

abbbbbbaaa baababaaab 10
1 2 1 0 0
2 7 8 4 7
2 3 9 2 8
3 4 6 1 1
0 8 5 2 4
2 8 10 4 7
7 10 1 0 0
1 4 6 0 2
0 9 8 0 6
4 8 5 0 1


Output

1 4 2 -1 2 4 10 1 1 5 

Note

Explanation of first sample case:

In the first question Sipa has two options: dabc (i = 0) and abdc (i = 2). The latter (abcd) is better than abdc, so answer is 2.

In the last question there is no i such that 0 ≤ i ≤ 1 and <image>.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 9;
int bound;
struct query {
  int l, r, x, y, k, id;
};
query qy[110000];
const int N = 2e5 + 10;
char str[N], S[N], T[N];
int sa[N], X[N], Y[N], b[N], a[N], h[N], r[N], rnk[N], fk[20][N], iden[20][N],
    lg[N], n, lcp[N], nn;
int num_q, len[2], ans[N], per[N], pos[N];
int ch[N];
int flag;
vector<int> vec[N];
bool need[N];
bool comp(int *r, int a, int b, int le) {
  return r[a] == r[b] && r[a + le] == r[b + le];
}
void sort(int *Rank, int *Id, int n, int m) {
  std::fill(b, b + m, 0);
  for (int i = n - 1; i >= 0; i--) b[Rank[i]]++;
  for (int i = 1; i < m; i++) b[i] += b[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--b[Rank[Id[i]]]] = Id[i];
}
void suffix(int n, int m = 500) {
  int *Rank = X, *Id = Y, p = 1;
  for (int i = 0; i < n; i++) Rank[i] = a[i], Id[i] = i;
  sort(Rank, Id, n, m);
  for (int j = 1; p < n; j <<= 1) {
    p = 0;
    for (int i = n - j; i < n; i++) Id[p++] = i;
    for (int i = 0; i < n; i++)
      if (sa[i] >= j) Id[p++] = sa[i] - j;
    sort(Rank, Id, n, p);
    std::swap(Rank, Id);
    Rank[sa[0]] = 0, p = 1;
    for (int i = 1; i < n; i++)
      Rank[sa[i]] = comp(Id, sa[i - 1], sa[i], j) ? p - 1 : p++;
    m = p;
  }
}
void LCP(char *str, int left, int right) {
  int i, j, k, len;
  len = right - left + 1;
  k = 0;
  for (i = left; i <= right; i++) {
    if (rnk[i] == len - 1)
      lcp[rnk[i]] = k = 0;
    else {
      if (k > 0) k--;
      j = sa[rnk[i] + 1];
      for (; str[i + k] == str[j + k]; k++)
        ;
      lcp[rnk[i]] = k;
    }
  }
}
int rmq(int id1, int id2) {
  int ip1, ip2, le, ri, id;
  if (id1 == id2) return n - id1;
  ip1 = id1;
  ip2 = id2;
  if (ip1 < ip2) {
    le = ip1;
    ri = ip2 - 1;
  } else {
    le = ip2;
    ri = ip1 - 1;
  }
  id = lg[ri - le + 1];
  int ret;
  if (fk[id][le] * flag < fk[id][ri + 1 - (1 << id)] * flag ||
      (fk[id][le] == fk[id][ri + 1 - (1 << id)] &&
       ch[iden[id][le]] <= ch[iden[id][ri + 1 - (1 << id)]]))
    return fk[id][le];
  return fk[id][ri + 1 - (1 << id)];
}
bool compare(int id1, int id2) {
  int i, j, s, p, q, dx, dy;
  bool ret, rev = false;
  if (id1 > id2) {
    rev = true;
    swap(id1, id2);
  }
  dx = min(id2 - id1, len[1]);
  dy = rmq(rnk[id1], rnk[len[0] + 1]);
  if (dy < dx)
    ret = rnk[id1] > rnk[len[0] + 1];
  else {
    if (id2 - id1 <= len[1]) {
      dx = len[1] - (id2 - id1);
      dy = rmq(rnk[len[0] + 1 + id2 - id1], rnk[len[0] + 1]);
      if (dy < dx)
        ret = rnk[len[0] + 1 + id2 - id1] < rnk[len[0] + 1];
      else {
        dx = id2 - id1;
        dy = rmq(rnk[id1], rnk[id1 + len[1] - id2 + len[0] + 1]);
        if (dy < dx)
          ret = rnk[id1] < rnk[id1 + len[1] - id2 + len[0] + 1];
        else
          ret = true;
      }
    } else {
      dx = id2 - (id1 + len[1]);
      dy = rmq(rnk[id1], rnk[id1 + len[1]]);
      if (dy < dx)
        ret = rnk[id1] < rnk[id1 + len[1]];
      else {
        dx = len[1];
        dy = rmq(rnk[id2 - len[1]], rnk[len[0] + 1]);
        if (dy < dx)
          ret = rnk[id2 - len[1]] < rnk[len[0] + 1];
        else
          ret = true;
      }
    }
  }
  ret ^= rev;
  return ret;
}
int rmq2(int id1, int id2) {
  int id = lg[id2 - id1 + 1];
  if (pos[iden[id][id1]] < pos[iden[id][id2 + 1 - (1 << id)]])
    return iden[id][id1];
  return iden[id][id2 + 1 - (1 << id)];
}
int main() {
  int t, i, j, s, p, q, k, id;
  flag = 1;
  for (i = 2; i <= 200000; i++) lg[i] = lg[i / 2] + 1;
  scanf("%s%s%d", S, T, &num_q);
  len[0] = strlen(S);
  len[1] = strlen(T);
  bound = 300;
  n = 0;
  for (i = 0; i < len[0]; i++) str[n++] = S[i];
  str[n++] = 'a' - 1;
  for (i = 0; i < len[1]; i++) str[n++] = T[i];
  for (i = 0; i < n; i++) a[i] = str[i];
  a[n] = 0;
  suffix(n + 1);
  for (i = 1; i <= n; i++) sa[i - 1] = sa[i];
  for (i = 0; i < n; i++) rnk[sa[i]] = i;
  LCP(str, 0, n - 1);
  for (i = 0; i < n; i++) {
    fk[0][i] = lcp[i];
    iden[0][i] = i;
  }
  for (k = 1; (1 << k) <= n; k++)
    for (i = 0; i + (1 << k) <= n; i++) {
      if (fk[k - 1][i] <= fk[k - 1][i + (1 << (k - 1))])
        fk[k][i] = fk[k - 1][i];
      else
        fk[k][i] = fk[k - 1][i + (1 << (k - 1))];
    }
  for (i = 0; i < num_q; i++) {
    scanf("%d%d%d%d%d", &qy[i].l, &qy[i].r, &qy[i].k, &qy[i].x, &qy[i].y);
    vec[qy[i].k].push_back(i);
  }
  for (i = 0; i <= len[0]; i++) per[i] = i;
  sort(per, per + len[0] + 1, compare);
  for (i = 0; i <= len[0]; i++) pos[per[i]] = i;
  memset(ans, -1, sizeof(ans));
  for (i = 1; i <= len[0]; i++) {
    if (i <= bound) {
      if (vec[i].size() == 0) continue;
      for (j = 0; j < i; j++) {
        int cnt = 0;
        for (s = 0; (s - 1) * i + j <= len[0]; s++) iden[0][s] = s * i + j;
        for (k = 1; (1 << (k - 1)) * i + j <= len[0]; k++)
          for (s = 0; (s + (1 << (k - 1))) * i + j <= len[0]; s++) {
            if (pos[iden[k - 1][s]] < pos[iden[k - 1][s + (1 << (k - 1))]])
              iden[k][s] = iden[k - 1][s];
            else
              iden[k][s] = iden[k - 1][s + (1 << (k - 1))];
          }
        for (s = 0; s < vec[i].size(); s++) {
          id = vec[i][s];
          if (qy[id].x <= j && qy[id].y >= j) {
            int lm, rm;
            lm = qy[id].l / i;
            rm = qy[id].r / i;
            if (qy[id].l % i > j) lm++;
            if (qy[id].r % i < j) rm--;
            if (lm <= rm) {
              int x = rmq2(lm, rm);
              if (ans[id] < 0)
                ans[id] = x;
              else {
                if (pos[ans[id]] > pos[x]) ans[id] = x;
              }
            }
          }
        }
      }
    } else {
      if (i == bound + 1) {
        for (j = 0; j <= len[0]; j++) iden[0][j] = j;
        for (k = 1; (1 << k) <= len[0] + 1; k++)
          for (j = 0; j + (1 << k) <= len[0] + 1; j++) {
            if (pos[iden[k - 1][j]] < pos[iden[k - 1][j + (1 << (k - 1))]])
              iden[k][j] = iden[k - 1][j];
            else
              iden[k][j] = iden[k - 1][j + (1 << (k - 1))];
          }
      }
      if (vec[i].size() == 0) continue;
      for (j = 0; j < vec[i].size(); j++) {
        id = vec[i][j];
        for (s = qy[id].l / i; s <= qy[id].r / i; s++) {
          int lm = max(qy[id].x, qy[id].l - s * i);
          int rm = min(qy[id].y, qy[id].r - s * i);
          lm = s * i + lm;
          rm = s * i + rm;
          if (lm <= rm) {
            int x = rmq2(lm, rm);
            if (ans[id] < 0)
              ans[id] = x;
            else {
              if (pos[ans[id]] > pos[x]) ans[id] = x;
            }
          }
        }
      }
    }
  }
  for (i = 0; i < num_q; i++) printf("%d\n", ans[i]);
  return 0;
}
