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 = 100005, G[2] = {998244353, 1000000007};
char s[maxn], t[maxn];
long long s_h[2][maxn], t_h[2][maxn], pol[2][maxn];
int ord[maxn], rk[maxn], L[maxn], R[maxn], X[maxn], Y[maxn], K[maxn], ans[maxn],
    n, len_s, len_t;
struct rmq {
  int a[18][maxn], Lg[maxn];
  void work() {
    for (int i = 2; i <= len_s + 1; i++) Lg[i] = Lg[i / 2] + 1;
    for (register int i = 1; i < 18; i++)
      for (register int j = 0; j + (1 << i) - 1 <= len_s; j++)
        a[i][j] = (a[i - 1][j] < a[i - 1][j + (1 << (i - 1))]
                       ? a[i - 1][j]
                       : a[i - 1][j + (1 << (i - 1))]);
  }
  void init() {
    for (int i = 0; i <= len_s; i++) a[0][i] = rk[i];
    work();
  }
  void init(int *b) {
    for (int i = 0; i <= len_s; i++) a[0][i] = rk[b[i]];
    work();
  }
  int query(int l, int r) {
    if (l > r) return (1 << 30);
    int p = Lg[r - l + 1];
    return (a[p][l] < a[p][r - (1 << p) + 1] ? a[p][l]
                                             : a[p][r - (1 << p) + 1]);
  }
} a, b;
char get_char(int p, int l) {
  if (l <= p) return s[l];
  if (l <= p + len_t) return t[l - p];
  return s[p + l - p - len_t];
}
bool cmp(int a, int b) {
  int l = 1, r = len_s + len_t, rr = r, tmp = 0;
  for (int mid; l <= r;) {
    mid = l + r >> 1;
    bool ok = 1;
    for (int i = 0; i < 2; i++) {
      long long va, vb;
      int l = mid, p = a;
      if (l <= p)
        va = s_h[i][l];
      else {
        va = s_h[i][p] * pol[i][l - p];
        if (l <= p + len_t)
          va = (va + t_h[i][l - p]);
        else {
          l -= p + len_t;
          va += t_h[i][len_t] * pol[i][l];
          va += s_h[i][p + l] - s_h[i][p] * pol[i][l];
        }
      }
      l = mid, p = b;
      if (l <= p)
        vb = s_h[i][l];
      else {
        vb = s_h[i][p] * pol[i][l - p];
        if (l <= p + len_t)
          vb = (vb + t_h[i][l - p]);
        else {
          l -= p + len_t;
          vb += t_h[i][len_t] * pol[i][l];
          vb += s_h[i][p + l] - s_h[i][p] * pol[i][l];
        }
      }
      if ((va - vb) % G[i]) {
        ok = 0;
        break;
      }
    }
    if (ok)
      tmp = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  if (tmp == rr) return a < b;
  return get_char(a, tmp + 1) < get_char(b, tmp + 1);
}
int main() {
  clock_t start, finish;
  start = clock();
  scanf("%s%s", s + 1, t + 1);
  len_s = strlen(s + 1), len_t = strlen(t + 1);
  for (int od = 0; od < 2; od++) {
    pol[od][0] = 1;
    for (int i = 1; i <= len_s; i++)
      s_h[od][i] = (s_h[od][i - 1] * 233ll + s[i] - 'a' + 1) % G[od],
      pol[od][i] = pol[od][i - 1] * 233ll % G[od];
    for (int i = 1; i <= len_t; i++)
      t_h[od][i] = (t_h[od][i - 1] * 233ll + t[i] - 'a' + 1) % G[od],
      pol[od][i] = pol[od][i - 1] * 233ll % G[od];
  }
  for (int i = 0; i <= len_s; i++) ord[i] = i;
  stable_sort(ord, ord + len_s + 1, cmp);
  for (int i = 0; i <= len_s; i++) rk[ord[i]] = i;
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++)
    scanf("%d%d%d%d%d", &L[i], &R[i], &K[i], &X[i], &Y[i]), ans[i] = (1 << 30);
  a.init();
  int cot = 0;
  for (int i = 1; i <= q; i++)
    if (ans[i] == (1 << 30)) {
      if (K[i] * 1ll * K[i] > len_s) {
        for (int p = 0; p * K[i] <= len_s; p++)
          ans[i] =
              (ans[i] < a.query(
                            max(L[i], p * K[i] + X[i]),
                            (R[i] < p * K[i] + Y[i] ? R[i] : p * K[i] + Y[i]))
                   ? ans[i]
                   : a.query(
                         max(L[i], p * K[i] + X[i]),
                         (R[i] < p * K[i] + Y[i] ? R[i] : p * K[i] + Y[i])));
      } else {
        static int pos[100005], lp[100005];
        int co = 0;
        for (int p = 0; p < K[i]; p++) {
          lp[p] = co;
          for (int j = p; j <= len_s; j += K[i]) pos[co++] = j;
        }
        ++cot;
        b.init(pos);
        for (int j = i; j <= q; j++)
          if (K[j] == K[i]) {
            int ll = L[j] / K[j], lpt = L[j] % K[j], rr = R[j] / K[j],
                rpt = R[j] % K[j];
            for (int p = X[j]; p <= Y[j]; p++) {
              int l = ll, r = rr;
              if (lpt > p) ++l;
              if (rpt < p) --r;
              ans[j] = (ans[j] < b.query(lp[p] + l, lp[p] + r)
                            ? ans[j]
                            : b.query(lp[p] + l, lp[p] + r));
            }
            if (ans[j] == (1 << 30)) ans[j] = -1;
          }
      }
      if (ans[i] == (1 << 30)) ans[i] = -1;
    }
  for (int i = 1; i <= q; i++) {
    if (ans[i] != -1) ans[i] = ord[ans[i]];
    printf("%d%c", ans[i], i == q ? '\n' : ' ');
  }
  finish = clock();
  cerr << (finish - start) / double(CLOCKS_PER_SEC) << endl;
  return 0;
}
