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 inf = 0x3f3f3f3f;
int q, Len, LenS, LenT;
int Log[200010], Min[200010][19];
int rk[200010], tp[200010], sa[200010], st[200010], height[200010], m = 75;
char S[100010], T[100010], str[200010];
int ans[100010], id[100010], _id[100010];
int Min2[100010][19];
int cntys[100010];
struct LYZ {
  int l, r, k, x, y, id;
} lyz[100010];
inline int read() {
  int x = 0, w = 0;
  char ch = 0;
  while (!isdigit(ch)) {
    w |= ch == '-';
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return w ? -x : x;
}
void radix_sort() {
  for (int i = 0; i <= m; st[i++] = 0)
    ;
  for (int i = 1; i <= Len; st[rk[i++]]++)
    ;
  for (int i = 1; i <= m; i++) st[i] += st[i - 1];
  for (int i = Len; i; i--) sa[st[rk[tp[i]]]--] = tp[i];
}
void suffix_sort() {
  for (int i = 1; i <= Len; i++) rk[i] = str[i] - '0', tp[i] = i;
  radix_sort();
  for (int k = 1, p = 0; p < Len; m = p, k <<= 1) {
    p = 0;
    for (int i = 1; i <= k; i++) tp[++p] = Len - k + i;
    for (int i = 1; i <= Len; i++)
      if (sa[i] > k) tp[++p] = sa[i] - k;
    radix_sort();
    memcpy(tp, rk, sizeof(int) * (Len + 5));
    rk[sa[1]] = p = 1;
    for (int i = 2; i <= Len; i++)
      rk[sa[i]] =
          (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + k] == tp[sa[i - 1] + k])
              ? p
              : ++p;
  }
}
void get_H() {
  for (int i = 1, j = 0, k = 0; i <= Len; i++) {
    if (rk[i] == 1) continue;
    if (k) k--;
    j = sa[rk[i] - 1];
    while (str[i + k] == str[j + k]) k++;
    height[rk[i]] = k;
  }
}
int lcp(int x, int y) {
  x = rk[x];
  y = rk[y];
  if (x > y) swap(x, y);
  x++;
  int t = Log[y - x + 1];
  return min(Min[x][t], Min[y - (1 << t) + 1][t]);
}
bool cmp(int n1, int n2) {
  bool flag = n1 > n2;
  if (n1 > n2) swap(n1, n2);
  if (n1 + LenT <= n2) {
    int Lcp = lcp(LenS + 1, n1 + 1);
    if (Lcp < LenT) return (rk[LenS + 1] < rk[n1 + 1]) ^ flag;
    Lcp = lcp(n1 + 1, n1 + LenT + 1);
    if (Lcp < n2 - (n1 + LenT)) return (rk[n1 + 1] < rk[n1 + LenT + 1]) ^ flag;
    Lcp = lcp(n2 - LenT + 1, LenS + 1);
    if (Lcp < LenT) return (rk[n2 - LenT + 1] < rk[LenS + 1]) ^ flag;
  } else {
    int Lcp = lcp(LenS + 1, n1 + 1);
    if (Lcp < n2 - n1) return (rk[LenS + 1] < rk[n1 + 1]) ^ flag;
    Lcp = lcp(LenS + n2 - n1 + 1, LenS + 1);
    if (Lcp < n1 + LenT - n2)
      return (rk[LenS + n2 - n1 + 1] < rk[LenS + 1]) ^ flag;
    Lcp = lcp(n1 + 1, LenS + n1 + LenT - n2 + 1);
    if (Lcp < n2 - n1)
      return (rk[n1 + 1] < rk[LenS + n1 + LenT - n2 + 1]) ^ flag;
  }
  return flag ^ 1;
}
int ask(int l, int r) {
  if (l > r) return inf;
  int t = Log[r - l + 1];
  return min(Min[l][t], Min[r - (1 << t) + 1][t]);
}
int ask2(int l, int r) {
  if (l > r) return inf;
  int t = Log[r - l + 1];
  return min(Min2[l][t], Min2[r - (1 << t) + 1][t]);
}
int main() {
  scanf("%s", S + 1);
  scanf("%s", T + 1);
  LenS = strlen(S + 1);
  LenT = strlen(T + 1);
  for (int i = 1; i <= LenS; i++) str[i] = S[i];
  for (int i = 1; i <= LenT; i++) str[i + LenS] = T[i];
  Len = LenS + LenT;
  suffix_sort();
  get_H();
  for (int i = 2; i <= Len; i++) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= Len; i++) Min[i][0] = height[i];
  for (int j = 1; j <= Log[Len]; j++)
    for (int i = 1; i <= Len - (1 << j) + 1; i++)
      Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
  iota(id, id + LenS + 1, 0);
  sort(id, id + LenS + 1, cmp);
  for (int i = 0; i <= LenS; i++) _id[id[i]] = i;
  memset(ans, 0x3f, sizeof ans);
  q = read();
  for (int i = 1; i <= q; i++) {
    int l = read(), r = read(), k = read(), x = read(), y = read();
    lyz[i] = (LYZ){l, r, k, x, y, i};
  }
  sort(lyz + 1, lyz + 1 + q, [&](LYZ& n1, LYZ& n2) { return n1.k < n2.k; });
  for (int i = 1; i <= q; i++) {
    if (lyz[i].k > 107) break;
    int ir = i;
    for (; ir < q && lyz[ir + 1].k == lyz[i].k; ir++)
      ;
    for (int ys = 0; ys < lyz[i].k; ys++) {
      int pos = ys;
      cntys[0] = 0;
      while (pos <= LenS) {
        cntys[++cntys[0]] = pos;
        pos += lyz[i].k;
      }
      for (int j = 1; j <= cntys[0]; j++) Min2[j][0] = _id[cntys[j]];
      for (int j = 1; j <= Log[cntys[0]]; j++)
        for (int ii = 1; ii <= cntys[0] - (1 << j) + 1; ii++)
          Min2[ii][j] = min(Min2[ii][j - 1], Min2[ii + (1 << (j - 1))][j - 1]);
      for (int j = i; j <= ir; j++)
        if (lyz[j].x <= ys && ys <= lyz[j].y) {
          int ll =
              lower_bound(cntys + 1, cntys + 1 + cntys[0], lyz[j].l) - cntys;
          int rr = upper_bound(cntys + 1, cntys + 1 + cntys[0], lyz[j].r) -
                   cntys - 1;
          ans[lyz[j].id] = min(ans[lyz[j].id], ask2(ll, rr));
        }
    }
    i = ir;
  }
  for (int i = 0; i <= LenS; i++) Min[i][0] = _id[i];
  for (int j = 1; j <= Log[LenS + 1]; j++)
    for (int i = 0; i <= LenS - (1 << j) + 1; i++)
      Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
  for (int i = 1; i <= q; i++)
    if (lyz[i].k > 107) {
      for (int j = 0; j * lyz[i].k <= LenS; j++) {
        ans[lyz[i].id] =
            min(ans[lyz[i].id], ask(max(lyz[i].l, j * lyz[i].k + lyz[i].x),
                                    min(lyz[i].r, j * lyz[i].k + lyz[i].y)));
      }
    }
  for (int i = 1; i <= q; i++)
    printf("%d%c", ans[i] < inf ? id[ans[i]] : -1, " \n"[i == q]);
}
