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 ST = 200200, MAXN = ST + 10;
long long _m[2] = {1000000021ll, 1000000009ll}, _p[2][MAXN];
struct hash {
  int N;
  long long cum[2][MAXN];
  void init(string s) {
    N = (int)s.size();
    if (!_p[0][0])
      for (int c = (0); c < (2); c++)
        for (int i = (0); i < (MAXN); i++)
          _p[c][i] = i ? _p[c][i - 1] * 137 % _m[c] : 1;
    for (int c = (0); c < (2); c++)
      for (int i = (0); i < (N); i++)
        cum[c][i] =
            (_p[c][i] * s[i] % _m[c] + (i ? cum[c][i - 1] : 0ll)) % _m[c];
  }
  inline long long qc(int l, int r, int c) {
    long long res = (cum[c][r] - (l ? cum[c][l - 1] : 0) + _m[c]) % _m[c];
    return res * _p[c][ST - l] % _m[c];
  }
  inline long long q(int l, int r) {
    return 1000000009ll * qc(l, r, 0) + qc(l, r, 1);
  }
} h;
int sa[200200], sv[200200];
struct suffix {
  int index;
  int rank[2];
};
int cmppp(suffix a, suffix b) {
  return (a.rank[0] == b.rank[0]) ? (a.rank[1] < b.rank[1] ? 1 : 0)
                                  : (a.rank[0] < b.rank[0] ? 1 : 0);
}
void buildSuffixArray(char *txt, int n) {
  suffix suffixes[n];
  for (int i = 0; i < n; i++) {
    suffixes[i].index = i;
    suffixes[i].rank[0] = txt[i] - 'a';
    suffixes[i].rank[1] = ((i + 1) < n) ? (txt[i + 1] - 'a') : -1;
  }
  sort(suffixes, suffixes + n, cmppp);
  int ind[n];
  for (int k = 4; k < 2 * n; k = k * 2) {
    int rank = 0;
    int prev_rank = suffixes[0].rank[0];
    suffixes[0].rank[0] = rank;
    ind[suffixes[0].index] = 0;
    for (int i = 1; i < n; i++) {
      if (suffixes[i].rank[0] == prev_rank &&
          suffixes[i].rank[1] == suffixes[i - 1].rank[1]) {
        prev_rank = suffixes[i].rank[0];
        suffixes[i].rank[0] = rank;
      } else {
        prev_rank = suffixes[i].rank[0];
        suffixes[i].rank[0] = ++rank;
      }
      ind[suffixes[i].index] = i;
    }
    for (int i = 0; i < n; i++) {
      int nextindex = suffixes[i].index + k / 2;
      suffixes[i].rank[1] =
          (nextindex < n) ? suffixes[ind[nextindex]].rank[0] : -1;
    }
    sort(suffixes, suffixes + n, cmppp);
  }
  for (int i = 0; i < n; i++) {
    sa[i] = suffixes[i].index, sv[sa[i]] = i;
  }
}
int N, M, Q, T, ord[100100], val[100100];
char s[100100], t[100100], tmp[200200];
int cs(int i, int j, int sz) {
  if (h.q(i, i + sz - 1) == h.q(j, j + sz - 1)) return -1;
  return sv[i] < sv[j];
}
bool comp(int i, int j) {
  bool swp = (i > j);
  if (swp) swap(i, j);
  int num = j - i;
  if (num >= M) {
    int x = cs(N, i, M);
    if (x != -1) return x ^ swp;
    if (num != M) {
      x = cs(i, j - (num - M), num - M);
      if (x != -1) return x ^ swp;
    }
    x = cs(j - M, N, M);
    if (x != -1) return x ^ swp;
  } else {
    int x = cs(N, i, num);
    if (x != -1) return x ^ swp;
    x = cs(N + M - (M - num), N, M - num);
    if (x != -1) return x ^ swp;
    x = cs(i, N + M - num, num);
    if (x != -1) return x ^ swp;
  }
  return !swp;
}
struct tree {
  int sz;
  vector<int> mn;
  void init(vector<int> v) {
    sz = int(v.size());
    for (int i = (0); i < (2 * sz); i++) mn.push_back(0);
    for (int i = (0); i < (sz); i++) mn[i + sz] = v[i];
    for (int i = sz - 1; i >= 1; i--) mn[i] = min(mn[i * 2], mn[i * 2 + 1]);
  }
  int qmn(int l, int r) {
    int res = 2e9;
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res = min(res, mn[l++]);
      if (r & 1) res = min(res, mn[--r]);
    }
    return res;
  }
} tr[55][55];
int lg[200200];
struct sparse {
  int sz;
  vector<int> mn[20];
  void init(vector<int> v) {
    int tt = int(v.size());
    sz = int(v.size());
    for (int j = (0); j < (tt); j++) mn[0].push_back(v[j]);
    for (int i = (1); i < (20); i++)
      for (int j = (0); j < (tt); j++)
        if (j + (1 << i) - 1 < tt) {
          mn[i].push_back(min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]));
        }
  }
  int qmn(int l, int r) {
    if (r < l) return N + 2;
    int k = lg[r - l + 1];
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
  }
} gen;
int main() {
  scanf("%s %s %d", s, t, &Q), N = int(strlen(s)), M = int(strlen(t));
  for (int i = (0); i < (N); i++) tmp[i] = s[i];
  for (int i = (N); i < (N + M); i++) tmp[i] = t[i - N];
  buildSuffixArray(tmp, N + M);
  h.init(string(tmp));
  for (int i = (2); i < (N + 5); i++) lg[i] = lg[i / 2] + 1;
  for (int i = (0); i < (N + 1); i++) ord[i] = i;
  sort(ord, ord + N + 1, comp);
  for (int i = (0); i < (N + 1); i++) val[ord[i]] = i;
  ord[N + 2] = -1;
  vector<int> fk;
  for (int i = (0); i < (N + 1); i++) fk.push_back(val[i]);
  gen.init(fk);
  for (int k = (0); k < (55); k++) {
    for (int st = (0); st < (k); st++) {
      vector<int> kk;
      for (int i = st; i < N + 1; i += k) {
        kk.push_back(val[i]);
      }
      tr[k][st].init(kk);
    }
  }
  for (int z = (0); z < (Q); z++) {
    int l, r, k, x, y, ans = N + 2;
    scanf("%d %d %d %d %d", &l, &r, &k, &x, &y);
    if (r / k - l / k + 1 <= 2000) {
      for (int i = (l / k); i < (r / k + 1); i++) {
        int L = max(l, x + i * k), R = min(r, y + i * k);
        ans = min(ans, gen.qmn(L, R));
      }
    } else {
      for (int i = (x); i < (y + 1); i++) {
        int L = l / k, R = r / k;
        while (i + k * L < l) L++;
        while (i + k * R > r) R--;
        ans = min(ans, tr[k][i].qmn(L, R + 1));
      }
    }
    printf("%d ", ord[ans]);
  }
  return 0;
}
