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 N = 400005;
char A[N], B[N], s[N];
int F[20][N], SA[N], rk[N];
int hei[N], x[N], y[N], c[N];
int lg[N], ans[N], id[N], val[N];
int n, m, Q;
int CMP(int a, int b, int k, int n) {
  return (y[a] != y[b] ||
          (a + k <= n ? y[a + k] : -1) != (b + k <= n ? y[b + k] : -1));
}
void buildSA(int n) {
  int m = 0;
  for (int i = (int)(1); i <= (int)(n); i++) {
    c[x[i] = s[i]]++;
    m = max(m, (int)(s[i]));
  }
  for (int i = (int)(1); i <= (int)(m); i++) c[i] += c[i - 1];
  for (int i = (int)(n); i >= (int)(1); i--) SA[c[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int p = 0;
    for (int i = (int)(n - k + 1); i <= (int)(n); i++) y[++p] = i;
    for (int i = (int)(1); i <= (int)(n); i++)
      if (SA[i] > k) y[++p] = SA[i] - k;
    for (int i = (int)(1); i <= (int)(p); i++) c[i] = 0;
    for (int i = (int)(1); i <= (int)(n); i++) c[x[y[i]]]++;
    for (int i = (int)(1); i <= (int)(p); i++) c[i] += c[i - 1];
    for (int i = (int)(n); i >= (int)(1); i--) SA[c[x[y[i]]]--] = y[i];
    swap(x, y);
    m = x[SA[1]] = 1;
    for (int i = (int)(2); i <= (int)(n); i++)
      x[SA[i]] = (m += CMP(SA[i], SA[i - 1], k, n));
    if (m == n) break;
  }
  for (int i = (int)(1); i <= (int)(n); i++) rk[SA[i]] = i;
  int j = 0;
  for (int i = (int)(1); i <= (int)(n); i++)
    if (rk[i] != 1) {
      for (; s[i + j] == s[SA[rk[i] - 1] + j]; j++)
        ;
      hei[rk[i]] = j;
      j -= (j != 0);
    }
  for (int i = (int)(1); i <= (int)(n); i++) F[0][i] = hei[i];
  for (int j = (int)(1); j <= (int)(18); j++)
    for (int i = (int)(1); i <= (int)(n - (1 << j) + 1); i++)
      F[j][i] = min(F[j - 1][i], F[j - 1][i + (1 << (j - 1))]);
}
int LCP(int x, int y) {
  if (x == y) return (1 << 29);
  x = rk[x];
  y = rk[y];
  if (x > y) swap(x, y);
  int k = lg[y - (++x) + 1];
  return min(F[k][x], F[k][y - (1 << k) + 1]);
}
bool cmp(int x, int y) {
  static int xl[3], xr[3], yl[3], yr[3];
  xl[0] = 1;
  xr[0] = x;
  xl[1] = n + 2;
  xr[1] = n + m + 1;
  xl[2] = x + 1;
  xr[2] = n;
  yl[0] = 1;
  yr[0] = y;
  yl[1] = n + 2;
  yr[1] = n + m + 1;
  yl[2] = y + 1;
  yr[2] = n;
  for (int i = 0, j = 0;;) {
    for (; i < 3 && xl[i] > xr[i]; i++)
      ;
    for (; j < 3 && yl[j] > yr[j]; j++)
      ;
    if (i == 3) return x < y;
    int len = LCP(xl[i], yl[j]);
    int mn = min(xr[i] - xl[i] + 1, yr[j] - yl[j] + 1);
    if (len >= mn)
      xl[i] += mn, yl[j] += mn;
    else
      return s[xl[i] + len] < s[yl[j] + len];
  }
}
struct que {
  int l, r, x, y, id;
};
vector<que> v[N];
vector<int> T[N];
int Mn(int x, int y) {
  if (x == -1) return y;
  if (y == -1) return x;
  return val[x] < val[y] ? x : y;
}
void solve1(int k) {
  for (int b = (int)(0); b <= (int)(k - 1); b++) T[b].clear();
  for (int i = (int)(0); i <= (int)(n); i++) T[i % k].push_back(i);
  for (int b = (int)(0); b <= (int)(k - 1); b++) {
    int sz = T[b].size() - 1;
    for (int i = (int)(0); i <= (int)(sz); i++) F[0][i] = T[b][i];
    for (int j = (int)(1); j <= (int)(18); j++)
      for (int i = (int)(0); i <= (int)(sz - (1 << j) + 1); i++)
        F[j][i] = Mn(F[j - 1][i], F[j - 1][i + (1 << (j - 1))]);
    for (int i = (int)(0); i <= (int)(v[k].size() - 1); i++) {
      que Q = v[k][i];
      if (Q.x <= b && b <= Q.y) {
        int l = Q.l / k, r = Q.r / k;
        l += (Q.l % k > b);
        r -= (Q.r % k < b);
        if (l <= r) {
          int k = lg[r - l + 1];
          ans[Q.id] = Mn(ans[Q.id], F[k][l]);
          ans[Q.id] = Mn(ans[Q.id], F[k][r - (1 << k) + 1]);
        }
      }
    }
  }
}
void solve2(int k) {
  for (int i = (int)(0); i <= (int)(v[k].size() - 1); i++) {
    que Q = v[k][i];
    for (int x = Q.x, y = Q.y; x <= n; x += k, y += k) {
      int l = max(x, Q.l), r = min(y, Q.r);
      if (l <= r) {
        int k = lg[r - l + 1];
        ans[Q.id] = Mn(ans[Q.id], F[k][l]);
        ans[Q.id] = Mn(ans[Q.id], F[k][r - (1 << k) + 1]);
      }
    }
  }
}
int main() {
  memset(ans, -1, sizeof(ans));
  ;
  for (int i = (int)(2); i <= (int)(N - 1); i++) lg[i] = lg[i / 2] + 1;
  scanf("%s%s%d", A + 1, B + 1, &Q);
  n = strlen(A + 1), m = strlen(B + 1);
  for (int i = (int)(1); i <= (int)(n); i++) s[i] = A[i];
  for (int i = (int)(1); i <= (int)(m); i++) s[i + n + 1] = B[i];
  s[n + 1] = '#';
  buildSA(n + m + 1);
  for (int i = (int)(0); i <= (int)(n); i++) id[i] = i;
  sort(id, id + n + 1, cmp);
  for (int i = (int)(0); i <= (int)(n); i++) val[id[i]] = i;
  for (int i = (int)(1); i <= (int)(Q); i++) {
    int l, r, k, x, y;
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    v[k].push_back((que){l, r, x, y, i});
  }
  int S = 70;
  for (int i = (int)(1); i <= (int)(S); i++) solve1(i);
  for (int i = (int)(0); i <= (int)(n); i++) F[0][i] = i;
  for (int j = (int)(1); j <= (int)(18); j++)
    for (int i = (int)(0); i <= (int)(n - (1 << j) + 1); i++)
      F[j][i] = Mn(F[j - 1][i], F[j - 1][i + (1 << (j - 1))]);
  for (int i = (int)(S + 1); i <= (int)(n); i++) solve2(i);
  for (int i = (int)(1); i <= (int)(Q); i++) printf("%d ", ans[i]);
}
