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>
#pragma GCC optimize "-O3"
using namespace std;
const long long MOD = 1e9 + 7;
struct hsh {
  unsigned long long a;
  long long b;
  hsh(long long x = 0) {
    a = x;
    b = x;
  }
  hsh(unsigned long long x, long long y) {
    a = x;
    b = y % MOD;
  }
  hsh operator+(hsh x) { return hsh(a + x.a, b + x.b); }
  hsh operator*(hsh x) { return hsh(a * x.a, b * x.b); }
  hsh operator-(hsh x) { return hsh(a - x.a, b - x.b + MOD); }
};
bool operator==(hsh a, hsh b) { return a.a == b.a && a.b == b.b; }
bool operator!=(hsh a, hsh b) { return a.a != b.a || a.b != b.b; }
const int MX = 120000;
const int LOG = 20;
const hsh P = 23917;
const int SQ = 300;
char s[MX], t[MX];
int spt[LOG][MX];
int pr[MX];
int bb[MX];
int bc;
int n, m;
hsh hss[MX];
hsh hst[MX];
hsh pw[MX];
int c[MX];
vector<int> vv;
int ans[MX];
vector<tuple<int, int, int, int, int> > go[MX];
hsh gethss(int l, int r) { return hss[r] - hss[l] * pw[r - l]; }
hsh gethst(int l, int r) { return hst[r] - hst[l] * pw[r - l]; }
int gss(int x, int y) {
  int l = 0;
  int r = min(n - x, n - y) + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (gethss(x, x + mid) == gethss(y, y + mid))
      l = mid;
    else
      r = mid;
  }
  return s[x + l] < s[y + l];
}
int gst(int x, int y) {
  int l = 0;
  int r = min(n - x, m - y) + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (gethss(x, x + mid) == gethst(y, y + mid))
      l = mid;
    else
      r = mid;
  }
  return s[x + l] < t[y + l];
}
int gts(int x, int y) { return 1 - gst(y, x); }
int gtt(int x, int y) {
  int l = 0;
  int r = min(m - x, m - y) + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (gethst(x, x + mid) == gethst(y, y + mid))
      l = mid;
    else
      r = mid;
  }
  return t[x + l] < t[y + l];
}
bool cmp(int x, int y) {
  int fl = 0;
  if (x > y) swap(x, y), fl = 1;
  if (x + m <= y) {
    if (hst[m] != gethss(x, x + m)) {
      return gts(0, x) ^ fl;
    } else if (gethss(x, x + (y - x - m)) !=
               gethss(x + m, x + m + (y - x - m))) {
      return gss(x, x + m) ^ fl;
    } else if (gethss(y - m, y) != hst[m]) {
      return gst(y - m, 0) ^ fl;
    } else {
      return (x < y) ^ fl;
    }
  } else {
    if (gethst(0, y - x) != gethss(x, y)) {
      return gts(0, x) ^ fl;
    } else if (gethst(y - x, m) != gethst(0, m - (y - x))) {
      return gtt(y - x, 0) ^ fl;
    } else if (gethss(x, y) != gethst(m - (y - x), m)) {
      return gst(x, m - (y - x)) ^ fl;
    } else {
      return (x < y) ^ fl;
    }
  }
}
int mmn(int a, int b) {
  if (a == -1) return b;
  if (b == -1) return a;
  if (c[a] < c[b]) return a;
  return b;
}
void build() {
  for (int i = 0; i < bc; ++i) spt[0][i] = bb[i];
  for (int i = 1; i < LOG; ++i)
    for (int j = 0; j + (1 << i) <= bc; ++j) {
      spt[i][j] = mmn(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
    }
}
int get(int l, int r) {
  if (r <= l) return -1;
  int k = pr[r - l];
  return mmn(spt[k][l], spt[k][r - (1 << k)]);
}
int q;
int main() {
  pw[0] = 1;
  for (int i = 1; i < MX; ++i) pw[i] = (pw[i - 1] * P);
  for (int i = 0; i < LOG; ++i) {
    for (int j = (1 << i); j < (1 << (i + 1)) && j < MX; ++j) pr[j] = i;
  }
  scanf("%s %s%d", s, t, &q);
  n = strlen(s);
  m = strlen(t);
  hss[0] = 0;
  for (int i = 0; i < n; ++i) hss[i + 1] = hss[i] * P + s[i];
  hst[0] = 0;
  for (int i = 0; i < m; ++i) hst[i + 1] = hst[i] * P + t[i];
  for (int i = 0; i <= n; ++i) vv.push_back(i);
  sort(vv.begin(), vv.end(), cmp);
  for (int i = 0; i < vv.size(); ++i) c[vv[i]] = i;
  for (int i = 0; i < vv.size(); ++i) bb[i] = i;
  bc = vv.size();
  build();
  for (int i = 0; i < q; ++i) ans[i] = -1;
  for (int i = 0; i < q; ++i) {
    int l, r, k, x, y;
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    ++r;
    if (k >= SQ) {
      int bst = -1;
      int lb = l / k;
      int rb = r / k + 1;
      for (int j = lb; j < rb; ++j)
        bst = mmn(bst, get(max(l, j * k + x), min(r, j * k + y + 1)));
      ans[i] = bst;
    } else {
      go[k].push_back(make_tuple(i, l, r, x, y));
    }
  }
  for (int i = 1; i < SQ; ++i) {
    if (go[i].empty()) continue;
    for (int j = 0; j < i; ++j) {
      bc = 0;
      for (int k = j; k <= n; k += i) {
        bb[bc++] = k;
      }
      build();
      for (auto it : go[i]) {
        int a, l, r, x, y;
        tie(a, l, r, x, y) = it;
        if (j >= x && j <= y)
          ans[a] = mmn(ans[a], get((l - j + i - 1) / i, (r - j + i - 1) / i));
      }
    }
  }
  for (int i = 0; i < q; ++i) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
