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;
inline char nchar() {
  static const int bufl = 1 << 20;
  static char buf[bufl], *a, *b;
  return a == b && (b = (a = buf) + fread(buf, 1, bufl, stdin), a == b) ? EOF
                                                                        : *a++;
}
inline int read() {
  int x = 0, f = 1;
  char c = nchar();
  for (; !isdigit(c); c = nchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = nchar()) x = x * 10 + c - '0';
  return x * f;
}
const int maxn = 1e5 + 10;
const int maxj = 17;
const int B = 70;
char s[maxn], t[maxn];
int n, m, a[maxn], b[maxn], back[maxn], ans[maxn], d[maxn << 1];
struct Q {
  int l, r, k, x, y, id;
} q[maxn];
inline void Min(int &x, int y) { x = min(x, y); }
inline int up(int x, int y) { return x / y + (bool)(x % y); }
inline int down(int x, int y) { return x / y; }
struct range {
  int f[maxn][maxj];
  void build(int a[], int n) {
    for (int i = 0; i <= n; ++i) f[i][0] = a[i];
    for (int j = 1; j < maxj; ++j)
      for (int i = 0; i <= n; ++i) {
        f[i][j] = f[i][j - 1];
        int x = i + (1 << (j - 1));
        if (x <= n) Min(f[i][j], f[x][j - 1]);
      }
  }
  int query(int l, int r) {
    if (l > r) return INT_MAX;
    int j = d[r - l + 1];
    return min(f[l][j], f[r - (1 << j) + 1][j]);
  }
} f, g;
void gen(int k) {
  for (int i = 0, st = 0, now = 0; i <= n;
       st += k, st = (st <= n ? st : ++now), ++i)
    b[i] = a[st];
  g.build(b, n);
}
namespace sa {
const int maxm = maxn << 1;
const int mj = 18;
int z[maxm], sa[maxm], rk[maxm], X[maxm], sum[maxm], h[maxm], len,
    rmq[maxm][mj];
inline void build() {
  for (int i = 1; i <= n; ++i) z[i] = s[i] - 'a' + 1;
  for (int i = 1; i <= m; ++i) z[n + i + 1] = t[i] - 'a' + 1;
  z[n + 1] = 30;
  len = n + m + 1;
  for (int i = 1; i <= len; ++i) ++sum[rk[i] = z[i]];
  for (int i = 1; i <= 30; ++i) sum[i] += sum[i - 1];
  for (int i = len; i; --i) sa[sum[rk[i]]--] = i;
  int p = rk[sa[1]] = 1;
  for (int i = 2; i <= len; ++i)
    rk[sa[i]] = (z[sa[i]] == z[sa[i - 1]] ? p : ++p);
  for (int j = 1; p < len; j <<= 1) {
    memset(sum, 0, (sizeof sum[0]) * (len + 1)), p = 0;
    for (int i = len - j + 1; i <= len; ++i) X[++p] = i;
    for (int i = 1; i <= len; ++i)
      if (sa[i] > j) X[++p] = sa[i] - j;
    for (int i = 1; i <= len; ++i) ++sum[rk[X[i]]];
    for (int i = 1; i <= len; ++i) sum[i] += sum[i - 1];
    for (int i = len; i; --i) sa[sum[rk[X[i]]]--] = X[i];
    memcpy(X, rk, (sizeof rk[0]) * (len + 1));
    p = rk[sa[1]] = 1;
    for (int i = 2; i <= len; ++i)
      rk[sa[i]] =
          (X[sa[i - 1]] == X[sa[i]] && X[sa[i - 1] + j] == X[sa[i] + j] ? p
                                                                        : ++p);
  }
  p = h[1] = 0;
  for (int i = 1; i <= len; ++i)
    if (rk[i] != 1)
      for (int &j = h[rk[i]] = (p -= (bool)p), &k = sa[rk[i] - 1];
           k + j <= len && i + j <= len && z[k + j] == z[i + j]; ++j, ++p)
        ;
  for (int i = 1; i <= len; ++i) rmq[i][0] = h[i];
  for (int j = 1; j < mj; ++j)
    for (int i = 1; i <= len; ++i) {
      rmq[i][j] = rmq[i][j - 1];
      int x = i + (1 << (j - 1));
      if (x <= len) Min(rmq[i][j], rmq[x][j - 1]);
    }
}
int lcp(int x, int y) {
  if (x == y) return len - x + 1;
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  ++x;
  int j = d[y - x + 1];
  return min(rmq[x][j], rmq[y - (1 << j) + 1][j]);
}
inline bool cmp(int x, int y) {
  bool fal = (x > y), ret;
  if (x > y) swap(x, y);
  if (x + m < y) {
    int fir = min(lcp(n + 2, x + 1), m);
    if (fir < m) {
      ret = (t[fir + 1] < s[x + fir + 1]);
      goto end;
    }
    int sec = min(lcp(x + 1, x + m + 1), y - (x + m));
    if (sec < y - (x + m)) {
      ret = (s[x + sec + 1] < s[x + m + sec + 1]);
      goto end;
    }
    int thr = min(lcp(y - m + 1, n + 2), m);
    if (thr < m) {
      ret = (s[y - m + thr + 1] < t[thr + 1]);
      goto end;
    }
    ret = (x < y);
  } else {
    int fir = min(lcp(n + 2, x + 1), y - x);
    if (fir < (y - x)) {
      ret = (t[fir + 1] < s[x + fir + 1]);
      goto end;
    }
    int sec = min(lcp(n + 2 + y - x, n + 2), x + m - y);
    if (sec < (x + m - y)) {
      ret = (t[y - x + sec + 1] < t[sec + 1]);
      goto end;
    }
    int thr = min(lcp(x + 1, n + 1 + x + m + 1 - y), y - x);
    if (thr < (y - x)) {
      ret = (s[x + thr + 1] < t[x + m - y + thr + 1]);
      goto end;
    }
    ret = (x < y);
  }
end:
  return fal ^ ret;
}
void run() {
  for (int i = 1; i <= n; ++i) back[i] = i;
  sort(back, back + n + 1, cmp);
  for (int i = 0; i <= n; ++i) a[back[i]] = i;
  f.build(a, n);
}
}  // namespace sa
int main() {
  for (int i = 2; i < (maxn << 1); ++i) d[i] = d[i >> 1] + 1;
  scanf("%s%s", s + 1, t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  sa::build();
  sa::run();
  int req = read();
  for (int i = 1; i <= req; ++i) {
    int l = read(), r = read(), k = read(), x = read(), y = read();
    q[i] = (Q){l, r, k, x, y, i};
  }
  sa::cmp(24, 34);
  sort(q + 1, q + req + 1, [](Q a, Q b) -> bool { return a.k < b.k; });
  for (int i = 1; i <= req; ++i) {
    int &ql = q[i].l, &qr = q[i].r, &k = q[i].k, &x = q[i].x, &y = q[i].y;
    int &as = ans[q[i].id] = INT_MAX;
    if (k <= B) {
      if (k != q[i - 1].k) gen(k);
      int spl = n % k, bef = 0, one = n / k;
      for (int r = 0; r < x; ++r) bef += one + (r <= spl);
      for (int r = x; r <= y; bef += one + (r <= spl), ++r) {
        if (qr < r) continue;
        int al = max(r, ql);
        int lef = up(al - r, k), rig = down(qr - r, k);
        int ret = g.query(bef + lef, bef + rig);
        Min(as, ret);
      }
    } else {
      for (int i = 0; i <= n; i += k) {
        int ret = f.query(max(i + x, ql), min(i + y, qr));
        Min(as, ret);
      }
    }
    as = (as == INT_MAX ? -1 : back[as]);
  }
  for (int i = 1; i <= req; ++i) printf("%d%c", ans[i], " \n"[i == req]);
  return 0;
}
