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 n, m, q, len, a[400005], b[400005], c[400005], w[400005], Ans[400005];
char s1[400005], s2[400005];
struct T {
  int x, y, k, l, r;
} Q[400005];
bool cmp1(int x, int y) { return Q[x].k < Q[y].k; }
int X[400005], Y[400005], SA[400005], Rk[400005], Ht[400005], v[400005],
    Min[400005][20], bit[20], lg[400005];
void GetSA(int a[], int n, int m = 256) {
  int *x = X, *y = Y, i, p, j;
  memset(v, 0, sizeof v);
  for (i = 1; i <= n; i++) v[x[i] = a[i]]++;
  for (i = 1; i <= m; i++) v[i] += v[i - 1];
  for (i = n; i >= 1; i--) SA[v[x[i]]--] = i;
  for (i = 1; i <= n; i <<= 1, m = p) {
    p = 0;
    memset(v, 0, sizeof v);
    for (j = n - i + 1; j <= n; j++) y[++p] = j;
    for (j = 1; j <= n; j++)
      if (SA[j] > i) y[++p] = SA[j] - i;
    for (j = 1; j <= n; j++) v[x[y[j]]]++;
    for (j = 1; j <= m; j++) v[j] += v[j - 1];
    for (j = n; j >= 1; j--) SA[v[x[y[j]]]--] = y[j];
    swap(x, y);
    p = 1;
    x[SA[1]] = 1;
    for (j = 2; j <= n; j++)
      if (y[SA[j - 1]] == y[SA[j]] && y[SA[j - 1] + i] == y[SA[j] + i])
        x[SA[j]] = p;
      else
        x[SA[j]] = ++p;
    if (p >= n) break;
  }
}
void GetHt(int a[], int n) {
  int k = 0;
  for (int i = 1; i <= n; i++) Rk[SA[i]] = i;
  for (int i = 1; i <= n; i++) {
    if (k) k--;
    int j = SA[Rk[i] - 1];
    while (i + k <= n && j + k <= n && a[i + k] == a[j + k]) k++;
    Ht[Rk[i]] = k;
  }
}
void Get(int n) {
  for (int i = 1; i <= n; i++) Min[i][0] = Ht[i];
  for (int i = 1; i <= lg[n]; i++)
    for (int j = 1; j + bit[i] - 1 <= n; j++)
      Min[j][i] = min(Min[j][i - 1], Min[j + bit[i - 1]][i - 1]);
}
int lcp(int x, int y) {
  if (Rk[x] > Rk[y]) swap(x, y);
  x = Rk[x];
  y = Rk[y];
  int t = lg[y - x];
  return min(Min[x + 1][t], Min[y - bit[t] + 1][t]);
}
int qry(int x, int y) {
  if (x > y) return 10000000;
  int t = lg[y - x];
  return min(Min[x][t], Min[y - bit[t] + 1][t]);
}
int comp(int x, int y, int l) {
  if (lcp(x, y) >= l) return 0;
  return (Rk[x] < Rk[y]) ? -1 : 1;
}
bool cmp(int x, int y) {
  int flag = x > y, t;
  if (flag) swap(x, y);
  if (m + x <= y) {
    t = comp(n + 1, x + 1, m);
    if (t) return (t < 0) ^ flag;
    t = comp(x + 1, x + m + 1, y - (x + m));
    if (t) return (t < 0) ^ flag;
    t = comp(y - m + 1, n + 1, m);
    if (t) return (t < 0) ^ flag;
  } else {
    t = comp(n + 1, x + 1, y - x);
    if (t) return (t < 0) ^ flag;
    t = comp(n + y - x + 1, n + 1, x + m - y);
    if (t) return (t < 0) ^ flag;
    t = comp(x + 1, m + n + x - y + 1, y - x);
    if (t) return (t < 0) ^ flag;
  }
  return flag ^ 1;
}
int main() {
  scanf("%s%s%d", s1 + 1, s2 + 1, &q);
  n = strlen(s1 + 1);
  m = strlen(s2 + 1);
  len = n + m;
  lg[1] = 0;
  bit[0] = 1;
  for (int i = 2; i <= len + 1; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= lg[len + 1]; i++) bit[i] = bit[i - 1] << 1;
  for (int i = 1; i <= n; i++) a[i] = s1[i];
  for (int i = 1; i <= m; i++) a[n + i] = s2[i];
  GetSA(a, len);
  GetHt(a, len);
  Get(len);
  for (int i = 0; i <= n; i++) b[i] = i;
  sort(b, b + n + 1, cmp);
  for (int i = 0; i <= n; i++) c[b[i]] = i;
  int sz = 80;
  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);
    w[i] = i;
    Ans[i] = 10000000;
  }
  sort(w + 1, w + q + 1, cmp1);
  for (int i = 1, j = 1; i <= sz && j <= q; i++)
    if (i == Q[w[j]].k) {
      int t = j;
      while (t < q && Q[w[t + 1]].k == i) t++;
      for (int l = 0; l < i; l++) {
        int tmp = (n + 1) / i + (l <= n % i);
        for (int i1 = 1; i1 <= tmp; i1++) Min[i1][0] = c[(i1 - 1) * i + l];
        for (int i1 = 1; i1 <= lg[tmp]; i1++)
          for (int j1 = 1; j1 + bit[i1] - 1 <= tmp; j1++)
            Min[j1][i1] = min(Min[j1][i1 - 1], Min[j1 + bit[i1 - 1]][i1 - 1]);
        for (int i1 = j; i1 <= t; i1++) {
          int s = w[i1];
          if (Q[s].x <= l && l <= Q[s].y)
            Ans[s] = min(Ans[s], qry((Q[s].l - l + i - 1) / i + 1,
                                     (Q[s].r - l + i) / i));
        }
      }
      j = t + 1;
    }
  for (int i = 1; i <= n + 1; i++) Min[i][0] = c[i - 1];
  for (int i = 1; i <= lg[n + 1]; i++)
    for (int j = 1; j + bit[i] - 1 <= n + 1; j++)
      Min[j][i] = min(Min[j][i - 1], Min[j + bit[i - 1]][i - 1]);
  for (int i = 1; i <= q; i++) {
    if (Q[i].k > sz) {
      int ans = 10000000;
      for (int j = 0; j * Q[i].k <= n; j++)
        ans = min(ans, qry(max(j * Q[i].k + Q[i].x, Q[i].l) + 1,
                           min(j * Q[i].k + Q[i].y, Q[i].r) + 1));
      Ans[i] = ans;
    }
    printf("%d ", Ans[i] != 10000000 ? b[Ans[i]] : -1);
  }
}
