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 maxn = 1e5 + 1, maxdn = maxn * 2, sq = 310, inf = 1e9, lg = 19;
int n, m, q, rnk[maxn];
int ql[maxn], qr[maxn], qx[maxn], qy[maxn], ans[maxn];
int c[maxdn], len, suf[maxdn][lg], lg2[maxdn], p[maxdn], sumc[maxdn], pn[maxdn],
    cn[maxdn], cnt[maxdn];
char s[maxdn], t[maxn];
int whole[lg][maxn];
struct Query {
  int l, id;
};
vector<Query> qs[maxn];
vector<int> small[sq];
int lcp(int i, int j) {
  i = c[i], j = c[j];
  if (i > j) swap(i, j);
  return min(suf[i][lg2[j - i]], suf[j - (1 << lg2[j - i])][lg2[j - i]]);
}
bool cmp(int i, int j) {
  bool rev = 0;
  if (i > j) rev = 1, swap(i, j);
  if (j - i >= m) {
    int st = lcp(i, n);
    if (st < m) return rev ^ (t[st] < s[i + st]);
    int ss = lcp(i, i + m);
    if (ss < j - i - m) return rev ^ (s[i + ss] < s[i + m + ss]);
    int ts = lcp(n, i + j - (i + m));
    if (ts < m) return rev ^ (s[i + j - (i + m) + ts] < t[ts]);
    return !rev;
  }
  int st = lcp(i, n);
  if (st < j - i) return rev ^ (t[st] < s[i + st]);
  int tt = lcp(n + j - i, n);
  if (tt < i + m - j) return rev ^ (t[j - i + tt] < t[tt]);
  int ts = lcp(n + m - (j - i), i);
  if (ts < j - i) return rev ^ (s[i + ts] < t[m - (j - i) + ts]);
  return !rev;
}
void get_ranks() {
  memcpy(s + n, t, sizeof t);
  len = n + m;
  s[len++] = '$';
  for (int i = 0; i < len; i++) cnt[s[i]]++;
  for (int i = 0; i < maxdn; i++) sumc[i + 1] = sumc[i] + cnt[i];
  for (int i = 0; i < len; i++) {
    p[sumc[s[i]]] = i;
    sumc[s[i]]++;
  }
  c[p[0]] = 0;
  for (int i = 1; i < len; i++)
    c[p[i]] = c[p[i - 1]] + !(s[p[i]] == s[p[i - 1]]);
  for (int mid = 1; mid <= len; mid *= 2) {
    for (int i = 0; i < len; i++)
      if ((p[i] -= mid) < 0) p[i] += len;
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < len; i++) cnt[c[i]]++;
    sumc[0] = 0;
    for (int i = 0; i < maxdn; i++) sumc[i + 1] = sumc[i] + cnt[i];
    for (int i = 0; i < len; i++) {
      pn[sumc[c[p[i]]]] = p[i];
      sumc[c[p[i]]]++;
    }
    cn[pn[0]] = 0;
    for (int i = 1; i < len; i++) {
      int j = pn[i] + mid, k = pn[i - 1] + mid;
      if (j >= len) j -= len;
      if (k >= len) k -= len;
      cn[pn[i]] = cn[pn[i - 1]] + !(c[pn[i]] == c[pn[i - 1]] && c[j] == c[k]);
    }
    copy(pn, pn + len, p), copy(cn, cn + len, c);
  }
  for (int i = 0, k = 0; i < len; i++)
    if (c[i] != len - 1) {
      for (int j = p[c[i] + 1]; s[i + k] == s[j + k];) k++;
      suf[c[i]][0] = k;
      if (k) k--;
    }
  for (int i = 2; i < len; i++) lg2[i] = lg2[i >> 1] + 1;
  for (int k = 1; k < lg; k++)
    for (int i = 0; i + (1 << k) < len; i++)
      suf[i][k] = min(suf[i][k - 1], suf[i + (1 << k - 1)][k - 1]);
  iota(p, p + n + 1, 0);
  sort(p, p + n + 1, cmp);
  for (int i = 0; i < n + 1; i++) whole[0][p[i]] = rnk[p[i]] = i;
}
int rmq[lg][maxn];
void solve(int k) {
  for (int g = 0; g < k; g++) {
    int sz = 0;
    for (int i = g; i < n + 1; i += k) rmq[0][sz++] = rnk[i];
    for (int k = 1; 1 << k <= sz; k++)
      for (int i = 0; i + (1 << k) <= sz; i++)
        rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << k - 1)]);
    for (int i = g; i < n + 1; i += k)
      for (auto q : qs[i])
        ans[q.id] = min({ans[q.id], rmq[lg2[i / k - q.l / k + 1]][q.l / k],
                         rmq[lg2[i / k - q.l / k + 1]]
                            [i / k + 1 - (1 << lg2[i / k - q.l / k + 1])]});
  }
}
int main() {
  scanf("%s %s %d", s, t, &q);
  n = strlen(s), m = strlen(t);
  get_ranks();
  for (int k = 1; k < lg; k++)
    for (int i = 0; i + (1 << k) <= n + 1; i++)
      whole[k][i] = min(whole[k - 1][i], whole[k - 1][i + (1 << k - 1)]);
  fill(ans, ans + q, inf);
  for (int qi = 0, l, r, k, x, y; qi < q; qi++) {
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    if (k == 1)
      ans[qi] = min(whole[lg2[r - l + 1]][l],
                    whole[lg2[r - l + 1]][r + 1 - (1 << lg2[r - l + 1])]);
    if (k >= sq) {
      for (int i = 0; i < n + 1; i += k) {
        int lef = max(l, i + x), ri = min(r, i + y);
        if (lef <= ri)
          ans[qi] = min(
              {ans[qi], whole[lg2[ri - lef + 1]][lef],
               whole[lg2[ri - lef + 1]][ri + 1 - (1 << lg2[ri - lef + 1])]});
      }
    } else {
      ql[qi] = l, qr[qi] = r, qx[qi] = x, qy[qi] = y;
      small[k].push_back(qi);
    }
  }
  for (int k = 2; k < sq; k++) {
    for (auto qi : small[k]) {
      int l = ql[qi], r = qr[qi], x = qx[qi], y = qy[qi];
      do {
        int lef = l % k <= x ? l + x - l % k : l + k - (l % k - x),
            ri = r % k >= x ? r - (r % k - x) : r - k + x - r % k;
        if (lef <= ri) qs[ri].push_back({lef, qi});
      } while (x++ < y);
    }
    solve(k);
    for (int i = 0; i < n + 1; i++) qs[i].clear();
  }
  for (int i = 0; i < q; i++) printf("%d ", ans[i] == inf ? -1 : p[ans[i]]);
  printf("\n");
  return 0;
}
