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;
int rk[200010], sa[200010], ht[200010];
int mn[200010][20];
char s[200010];
namespace SA {
int head[200010 * 2];
pair<pair<int, int>, int> pos[200010 * 2], buf[200010 << 1], tbuf[200010 << 1];
int nxt[200010 * 2];
void bucket_sort(int ok, int n) {
  int i, u, j, deg, E, K;
  for (i = E = K = 0; i < max(222, n + 10); i++) head[i] = -1;
  for (i = 0; i < n; i++) {
    if (ok)
      u = pos[i].first.first + 1;
    else
      u = pos[i].first.second + 1;
    buf[E] = pos[i];
    nxt[E] = head[u];
    head[u] = E++;
  }
  for (int i = 0; i < max(n + 10, 222); i++) {
    for (deg = 0, j = head[i]; ~j; j = nxt[j]) {
      tbuf[deg++] = buf[j];
    }
    while (deg) pos[K++] = tbuf[--deg];
  }
}
void LCP(int n) {
  for (int i = 1; i < n; i++) mn[i][1] = ht[i + 1];
  for (int j = 2; j < 20; j++) {
    for (int i = 1; i <= n; i++) {
      if (i + (1 << j) - 1 > n) continue;
      mn[i][j] = min(ht[i + (1 << (j - 1))],
                     min(mn[i][j - 1], mn[min(n, i + (1 << j - 1))][j - 1]));
    }
  }
}
void height(int n) {
  int h = 0, i;
  for (i = 0; i < n; i++) sa[rk[i]] = i;
  for (i = 0; i < n; i++) {
    if (rk[i] == 1) continue;
    h = max(0, h - 1);
    for (int j = sa[rk[i] - 1]; s[i + h] == s[j + h]; h++)
      ;
    ht[rk[i]] = h;
  }
}
void buildSA(int n) {
  int i, j, cnt, u;
  for (i = 0; i < n; i++) rk[i] = s[i];
  rk[n] = 0;
  for (i = 0; i < 20; i++) {
    for (j = 0; j < n; j++)
      pos[j] = pair<pair<int, int>, int>(
          pair<int, int>(rk[j], rk[min(n, j + (1 << i))]), j);
    bucket_sort(0, n);
    bucket_sort(1, n);
    pos[n] = pair<pair<int, int>, int>(pair<int, int>(-1, -1), -1);
    for (cnt = j = 0; j < n; j++) {
      rk[pos[j].second] = cnt + 1;
      cnt += (pos[j].first != pos[j + 1].first);
    }
    if (cnt == n) break;
  }
  height(n);
  LCP(n);
}
int calc(int u, int v) {
  if (u > v) swap(u, v);
  int l = 31 - __builtin_clz(v - u + 1);
  return min(mn[u][l], mn[v - (1 << l) + 1][l]);
}
}  // namespace SA
int n, len, lent;
char t[200010];
int a, b, aa, bb;
int id[200010];
bool cmp(int first, int second) {
  if (first > second) {
    if (cmp(second, first)) return false;
    return true;
  }
  a = rk[n];
  b = rk[first];
  if (SA::calc(a, b) < min(lent, second - first)) return a < b;
  if (lent == second - first) return true;
  if (lent > second - first) {
    aa = rk[n + second - first];
    bb = rk[n];
    if (SA::calc(aa, bb) < lent - (second - first)) return aa < bb;
    aa = rk[first];
    bb = rk[len - (second - first)];
    if (SA::calc(aa, bb) < second - first) return aa < bb;
    return true;
  }
  aa = rk[first];
  bb = rk[first + lent];
  if (SA::calc(aa, bb) < second - first - lent) return aa < bb;
  aa = rk[second - lent];
  bb = rk[n];
  if (SA::calc(aa, bb) < lent) return aa < bb;
  return true;
}
vector<int> qu[316];
vector<pair<int, int> > v[200010];
int l[200010], r[200010], first[200010], second[200010];
pair<int, int> ans[200010];
int f[200010];
pair<int, int> rmq[200010][20];
pair<int, int> calc_min(int u, int v) {
  int rr = 31 - __builtin_clz(v - u + 1);
  return min(rmq[u][rr], rmq[v - (1 << rr) + 1][rr]);
}
int nxt[200010];
int pre[200010];
int find_root(int u) {
  if (nxt[u] == u) return u;
  return nxt[u] = find_root(nxt[u]);
}
int main() {
  scanf("%s", s);
  scanf("%s", t);
  n = strlen(s);
  len = n;
  lent = strlen(t);
  for (int i = 0; i < lent; i++) s[len++] = t[i];
  SA::buildSA(len);
  for (int i = 0; i <= n; i++) id[i] = i;
  sort(id, id + n + 1, cmp);
  for (int i = 0; i <= n; i++) f[id[i]] = i;
  for (int j = 0; j < 20; j++) {
    for (int i = 0; i <= n; i++) {
      if (i + (1 << j) - 1 > n) break;
      if (!j)
        rmq[i][j] = pair<int, int>(f[i], i);
      else
        rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int k;
    scanf("%d%d%d%d%d", &l[i], &r[i], &k, &first[i], &second[i]);
    ans[i] = pair<int, int>(n + 1, 0);
    int xx = first[i], yy = second[i];
    if (k >= 316) {
      ans[i] = pair<int, int>(n + 1, 0);
      for (int j = 1; j <= n / k + 2; j++) {
        int st = max(xx, l[i]);
        int ed = min(yy, r[i]);
        if (st <= ed) ans[i] = min(ans[i], calc_min(st, ed));
        xx += k;
        yy += k;
      }
    } else {
      ans[i] = pair<int, int>(n + 1, 0);
      qu[k].push_back(i);
    }
  }
  for (int k = 1; k < 316; k++) {
    for (int ID : qu[k]) {
      int Ll = l[ID], Rr = r[ID];
      for (int j = first[ID]; j <= second[ID]; j++) {
        int L = Ll, R = Rr;
        int rr = j;
        if (L % k <= rr)
          L = k * (L / k) + rr;
        else
          L = k * (L / k + 1) + rr;
        if (R % k >= rr)
          R = k * (R / k) + rr;
        else
          R = k * (R / k - 1) + rr;
        if (L > R) continue;
        v[R].push_back(pair<int, int>(L, ID));
      }
    }
    for (int rr = 0; rr < k; rr++) {
      for (int i = rr; i <= n; i += k) {
        nxt[i] = i;
        int st = i - k;
        while (st >= 0 && f[st] >= f[i]) {
          nxt[st] = i;
          st = pre[st];
        }
        pre[i] = st;
        for (int j = 0; j < v[i].size(); j++) {
          int ID = v[i][j].second;
          int jd = find_root(v[i][j].first);
          ans[ID] = min(ans[ID], pair<int, int>(f[jd], jd));
        }
        v[i].clear();
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    if (ans[i].first != n + 1)
      printf("%d ", ans[i].second);
    else
      printf("%d ", -1);
  }
  return 0;
}
