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 IN() {
  int c, f, x;
  while (!isdigit(c = getchar()) && c != '-')
    ;
  c == '-' ? (f = 1, x = 0) : (f = 0, x = c - '0');
  while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + c - '0';
  return !f ? x : -x;
}
const int N = 400000 + 19;
const int oo = (1 << 30) - 1;
char A[N], B[N], s[N];
int F[20][N];
int SA[N], rk[N], h[N], Lg[N], id[N], ans[N], val[N];
int n, m, q;
void Build_SA(int n) {
  static int tmp[N], cnt[N], trk[N], p;
  for (int i = 1; i < n + 1; i++) cnt[s[i]]++, p = max(p, int(s[i]));
  for (int i = 1; i < p + 1; i++) cnt[i] += cnt[i - 1];
  for (int i = n; i; i--) SA[cnt[s[i]]--] = i;
  rk[SA[1]] = p = 1;
  for (int i = 2; i < n + 1; i++)
    rk[SA[i]] = (s[SA[i]] == s[SA[i - 1]] ? p : ++p);
  for (int k = 1; k <= n; k <<= 1) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i < n + 1; i++) cnt[rk[i + k]]++;
    for (int i = 1; i < p + 1; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) tmp[cnt[rk[i + k]]--] = i;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i < n + 1; i++) cnt[rk[i]]++;
    for (int i = 1; i < p + 1; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i; i--) SA[cnt[rk[tmp[i]]]--] = tmp[i];
    trk[SA[1]] = p = 1;
    for (int i = 2; i < n + 1; i++) {
      trk[SA[i]] =
          (rk[SA[i]] == rk[SA[i - 1]] && rk[SA[i] + k] == rk[SA[i - 1] + k]
               ? p
               : ++p);
    }
    memcpy(rk, trk, sizeof(trk));
  }
  for (int i = 1, j = 0; i <= n; i++) {
    if (rk[i] == 1) continue;
    while (s[i + j] == s[SA[rk[i] - 1] + j]) j++;
    h[rk[i]] = j;
    if (j) j--;
  }
  for (int i = 1; i < n + 1; i++) F[0][i] = h[i];
  for (int x = 1; x < 20; x++) {
    for (int i = 1; i + (1 << x) - 1 <= n; i++) {
      F[x][i] = min(F[x - 1][i], F[x - 1][i + (1 << x - 1)]);
    }
  }
}
int LCP(int x, int y) {
  if (x == y) return oo;
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  x++;
  int t = Lg[y - x + 1];
  return min(F[t][x], F[t][y - (1 << t) + 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 QType {
  int l, r, x, y, id;
};
vector<QType> V[N];
int l, r, x, y, k, S;
vector<int> T[N];
int cal(int x, int y) {
  if (x == -1) return y;
  if (y == -1) return x;
  return val[x] < val[y] ? x : y;
}
void Work1(int k) {
  for (int i = 0; i < n + 1; i++) T[i % k].push_back(i);
  for (int b = 0; b < k; b++) {
    for (int i = 0; i < T[b].size(); i++) F[0][i] = T[b][i];
    for (int x = 1; x < 20; x++) {
      for (int i = 0; i + (1 << x) - 1 < T[b].size(); i++) {
        F[x][i] = cal(F[x - 1][i], F[x - 1][i + (1 << x - 1)]);
      }
    }
    for (QType Q : V[k])
      if (Q.x <= b && b <= Q.y) {
        int l = Q.l / k, r = Q.r / k;
        if (Q.l % k > b) l++;
        if (Q.r % k < b) r--;
        if (l <= r) {
          int t = Lg[r - l + 1];
          ans[Q.id] = cal(ans[Q.id], F[t][l]);
          ans[Q.id] = cal(ans[Q.id], F[t][r - (1 << t) + 1]);
        }
      }
  }
  for (int i = 0; i < k; i++) T[i].clear();
}
void Work2(int k) {
  for (QType Q : V[k]) {
    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 t = Lg[r - l + 1];
        ans[Q.id] = cal(ans[Q.id], F[t][l]);
        ans[Q.id] = cal(ans[Q.id], F[t][r - (1 << t) + 1]);
      }
    }
  }
}
int main() {
  memset(ans, -1, sizeof(ans));
  for (int i = 2; i < N; i++) Lg[i] = Lg[i >> 1] + 1;
  scanf("%s%s%d", A + 1, B + 1, &q);
  n = strlen(A + 1);
  m = strlen(B + 1);
  for (int i = 1; i < n + 1; i++) s[i] = A[i];
  s[n + 1] = '#';
  for (int i = 1; i < m + 1; i++) s[i + n + 1] = B[i];
  Build_SA(n + m + 1);
  for (int i = 0; i < n + 1; i++) id[i] = i;
  sort(id, id + n + 1, cmp);
  for (int i = 0; i < n + 1; i++) val[id[i]] = i;
  for (int i = 1; i < q + 1; i++) {
    l = IN(), r = IN(), k = IN(), x = IN(), y = IN();
    V[k].push_back((QType){l, r, x, y, i});
  }
  S = 70;
  for (int i = 1; i < S + 1; i++) Work1(i);
  for (int i = 0; i < n + 1; i++) F[0][i] = i;
  for (int x = 1; x < 20; x++) {
    for (int i = 0; i + (1 << x) - 1 <= n; i++) {
      F[x][i] = cal(F[x - 1][i], F[x - 1][i + (1 << x - 1)]);
    }
  }
  for (int i = S + 1; i < n + 1; i++) Work2(i);
  for (int i = 1; i < q + 1; i++) printf("%d ", ans[i]);
  puts("");
}
