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>
const int N = 400005, inf = 1000000000;
using namespace std;
int n, m, Ans[N], a[N], b[N], c[N], Q, p[N], id[N], wa[N], wb[N], wd[N], h[N],
    sa[N], rk[N];
char S[N], T[N];
bool Cmpsm(int *r, int a, int b, int l) {
  return (r[a] == r[b] && r[a + l] == r[b + l]);
}
void Getsa(int *r, int n, int m) {
  int k, i, j, p, *x = wa, *y = wb, *t;
  for (i = 1; i <= n; i++) wd[x[i] = r[i]]++;
  for (i = 1; i <= m; i++) wd[i] += wd[i - 1];
  for (i = n; i >= 1; i--) sa[wd[x[i]]--] = i;
  for (j = 1; j <= n; j *= 2, m = p) {
    for (p = 0, i = n - j + 1; i <= n; i++) y[++p] = i;
    for (i = 1; i <= n; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (i = 0; i <= m; i++) wd[i] = 0;
    for (i = 1; i <= n; i++) wd[x[y[i]]]++;
    for (i = 1; i <= m; i++) wd[i] += wd[i - 1];
    for (i = n; i >= 1; i--) sa[wd[x[y[i]]]--] = y[i];
    for (t = x, x = y, y = t, x[sa[1]] = p = 0, i = 2; i <= n; i++)
      if (Cmpsm(y, sa[i], sa[i - 1], j))
        x[sa[i]] = p;
      else
        x[sa[i]] = ++p;
  }
  for (i = 1; i <= n; i++) rk[sa[i]] = i;
  for (k = 1, i = 1; i < n; h[rk[i]] = k, i++)
    for ((k ? k-- : 0), j = sa[rk[i] - 1]; r[i + k] == r[j + k]; k++)
      ;
}
int rq[N][19], lg[N];
void Buildrmq(int *a, int n) {
  for (int j = 1, i = 2; i <= n; i++) {
    if (i >= (1 << (j + 1))) j++;
    lg[i] = j;
  }
  for (int i = 0; i <= n; i++) rq[i][0] = a[i];
  for (int j = 1; j <= 18; j++)
    for (int i = 1 << (j - 1); i <= n; i++)
      rq[i][j] = min(rq[i][j - 1], rq[i - (1 << (j - 1))][j - 1]);
}
int Askrmq(int l, int r) {
  int res = inf;
  if (l > r) return (inf);
  while (l <= r) {
    res = min(res, rq[r][lg[r - l + 1]]);
    r -= (1 << lg[r - l + 1]);
  }
  return (res);
}
struct Que {
  int l, r, k, x, y, t;
} q[N];
int Asklcp(int a, int b) {
  if (rk[a] > rk[b]) swap(a, b);
  if (a == b) return (inf);
  return (Askrmq(rk[a] + 1, rk[b]));
}
int Compare(int a, int b) {
  int f = 1;
  if (a > b) swap(a, b), f = -1;
  if (a == b) return (0);
  if (b - a >= m) {
    int lcp = Asklcp(n + 1, a + 1);
    if (lcp < m) {
      if (rk[n + 1] < rk[a + 1]) return (f);
      return (-f);
    }
    lcp = Asklcp(a + 1, a + m + 1);
    if (lcp < b - a - m) {
      if (rk[a + 1] < rk[a + m + 1]) return (f);
      return (-f);
    }
    lcp = Asklcp(b - m + 1, n + 1);
    if (lcp < m) {
      if (rk[b - m + 1] < rk[n + 1]) return (f);
      return (-f);
    }
  } else {
    int lcp = Asklcp(n + 1, a + 1);
    if (lcp < b - a) {
      if (rk[n + 1] < rk[a + 1]) return (f);
      return (-f);
    }
    lcp = Asklcp(n + b - a + 1, n + 1);
    if (lcp < m - b + a) {
      if (rk[n + b - a + 1] < rk[n + 1]) return (f);
      return (-f);
    }
    lcp = Asklcp(a + 1, n + m - b + a + 1);
    if (lcp < b - a) {
      if (rk[a + 1] < rk[n + m + 1 - b + a]) return (f);
      return (-f);
    }
  }
  return (0);
}
bool Cmp(int a, int b) {
  int rs = Compare(a, b);
  if (rs == 1) return (1);
  if (rs == -1) return (0);
  return (a < b);
}
bool Cmpk(Que a, Que b) { return (a.k < b.k); }
int main() {
  scanf("%s%s%d", S + 1, T + 1, &Q);
  n = strlen(S + 1), m = strlen(T + 1);
  for (int i = 1; i <= n; i++) c[i] = S[i] - 'a' + 1;
  for (int i = 1; i <= m; i++) c[i + n] = T[i] - 'a' + 1;
  Getsa(c, n + m + 1, 27);
  Buildrmq(h, n + m + 1);
  for (int i = 0; i <= n; i++) a[i] = i;
  sort(a, a + 1 + n, Cmp);
  for (int i = 0; i <= n; i++) b[a[i]] = i;
  for (int i = 1; i <= Q; i++)
    scanf("%d%d%d%d%d", &q[i].l, &q[i].r, &q[i].k, &q[i].x, &q[i].y);
  for (int i = 1; i <= Q; i++) q[i].t = i, Ans[i] = inf;
  sort(q + 1, q + 1 + Q, Cmpk);
  int l = 0, r = 0;
  for (int k = 1; k * k <= n; k++) {
    while (q[l].k < k && l <= Q) l++;
    while (q[r].k <= k && r <= Q) r++;
    if (k != q[l].k) continue;
    for (int i = 0; i < k; i++) {
      int tot = -1;
      for (int j = i; j <= n; j += k) p[++tot] = b[j];
      Buildrmq(p, tot);
      for (int j = l; j < r; j++)
        if (q[j].x <= i && i <= q[j].y) {
          int L = (q[j].l - i) / k;
          if (L * k + i < q[j].l) L++;
          int R = (q[j].r - i) / k;
          if ((R + 1) * k + i <= q[j].r) R++;
          if (R * k + i <= q[j].r)
            Ans[j] = min(Ans[j], Askrmq(max(0, L), min(R, tot)));
        }
    }
  }
  Buildrmq(b, n);
  for (int i = r; i <= Q; i++)
    for (int t = 0; t * q[i].k + q[i].x <= n; t++) {
      int L = t * q[i].k + q[i].x, R = t * q[i].k + q[i].y;
      if (R < q[i].l || q[i].r < L) continue;
      Ans[i] = min(Ans[i], Askrmq(max(q[i].l, L), min(q[i].r, R)));
    }
  for (int i = 1; i <= Q; i++) id[q[i].t] = ((Ans[i] < inf) ? a[Ans[i]] : -1);
  for (int i = 1; i <= Q; i++) printf("%d\n", id[i]);
}
