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 EMAX = 2;
const int LMAX = 18;
const int SQRT = 65;
const int NMAX = 200005;
string str;
vector<int> stk[SQRT][SQRT];
tuple<int, int, int, int, int> qry[NMAX];
int lgr[NMAX], lst[NMAX][EMAX], aux[NMAX], psm[NMAX], ord[NMAX];
int sfa[LMAX][NMAX], spt[LMAX][NMAX], arr[NMAX], ans[NMAX], lis[NMAX];
inline int lcp(int x, int y, int n) {
  if (x == y) return n - x + 1;
  int ans = 0;
  for (int k = lgr[n]; k >= 0; k--)
    if (sfa[k][x] == sfa[k][y]) ans += (1 << k), x += (1 << k), y += (1 << k);
  return ans;
}
inline int rmq(int l, int r) {
  if (l > r) return numeric_limits<int>::max() >> 1;
  int p = lgr[r - l + 1];
  return min(spt[p][l], spt[p][r - (1 << p) + 1]);
}
int N, M;
inline bool cmp(int x, int y) {
  bool oki = (x > y);
  int aux = -1;
  if (x > y) swap(x, y);
  if (y - x >= M) {
    aux = lcp(N + 1, x + 1, N + M);
    if (aux < M) return (str[N + 1 + aux] < str[x + 1 + aux]) ^ oki;
    aux = lcp(x + 1, x + M + 1, N + M);
    if (aux < y - M - x) return (str[x + 1 + aux] < str[x + M + 1 + aux]) ^ oki;
    aux = lcp(y - M + 1, N + 1, N + M);
    if (aux < M) return (str[y - M + 1 + aux] < str[N + 1 + aux]) ^ oki;
  } else {
    aux = lcp(N + 1, x + 1, N + M);
    if (aux < y - x) return (str[N + 1 + aux] < str[x + 1 + aux]) ^ oki;
    aux = lcp(N + y - x + 1, N + 1, N + M);
    if (aux < M - y + x)
      return (str[N + y - x + 1 + aux] < str[N + 1 + aux]) ^ oki;
    aux = lcp(x + 1, N + M - y + x + 1, N + M);
    if (aux < y - x)
      return (str[x + 1 + aux] < str[N + M - y + x + 1 + aux]) ^ oki;
  }
  return (x < y) ^ oki;
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie();
  cout.tie();
  string str1, str2;
  int q;
  cin >> str1 >> str2 >> q;
  str = " " + str1 + str2;
  int n = (int)str1.length(), m = (int)str2.length();
  for (int i = 2; i <= n + m; i++) lgr[i] = lgr[i >> 1] + 1;
  for (int i = 1; i <= n + m; ++i) sfa[0][i] = str[i] - 'a' + 1;
  for (int l = 1; (1 << (l - 1)) <= n + m; l++) {
    for (int i = 1, j = 1 + (1 << (l - 1)); i <= n + m; i++, j++) {
      lst[i][0] = sfa[l - 1][i];
      arr[i] = i;
      lst[i][1] = (j <= n + m) ? sfa[l - 1][j] : 0;
    }
    for (int k = 1; k >= 0; k--) {
      memset(psm, 0, max(27, n + m + 1) << 2);
      for (int i = 1; i <= n + m; i++) psm[lst[arr[i]][k]]++;
      for (int i = 1; i <= max(26, n + m + 1); i++) psm[i] += psm[i - 1];
      for (int i = n + m; i >= 1; i--) aux[psm[lst[arr[i]][k]]--] = arr[i];
      memcpy(arr, aux, (n + m + 1) << 2);
    }
    sfa[l][arr[1]] = 1;
    for (int i = 2; i <= n + m; i++) {
      sfa[l][arr[i]] = sfa[l][arr[i - 1]];
      if (memcmp(lst[arr[i - 1]], lst[arr[i]], 8) != 0) sfa[l][arr[i]]++;
    }
  }
  N = n, M = m;
  iota(ord, ord + n + 1, 0);
  sort(ord, ord + n + 1, cmp);
  for (int i = 0; i <= n; i++) lis[ord[i]] = i;
  for (int i = 0; i <= n; i++) spt[0][i] = lis[i];
  for (int l = 1; (1 << l) <= n + 1; l++)
    for (int i = 0, j = (1 << (l - 1)); j <= n; i++, j++)
      spt[l][i] = min(spt[l - 1][i], spt[l - 1][j]);
  for (int t = 1; t <= q; t++) {
    int l, r, k, x, y;
    cin >> l >> r >> k >> x >> y;
    qry[t] = tie(l, r, k, x, y);
    ans[t] = numeric_limits<int>::max() >> 1;
    if (k >= SQRT) {
      for (int i = x, j = y; i <= n; i += k, j += k)
        ans[t] = min(ans[t], rmq(max(i, l), min(j, r)));
    } else {
      for (int i = x; i <= y; i++) stk[k][i].push_back(t);
    }
  }
  for (int k = 1; k < SQRT; k++) {
    for (int t = 0; t < k; t++) {
      if (stk[k][t].size() == 0) continue;
      int aux = -1;
      for (int i = t; i <= n; i += k) spt[0][++aux] = lis[i];
      for (int l = 1; (1 << l) <= aux + 1; l++)
        for (int i = 0, j = (1 << (l - 1)); j <= aux + 1; i++, j++)
          spt[l][i] = min(spt[l - 1][i], spt[l - 1][j]);
      for (int qr : stk[k][t]) {
        int l, r, k, x, y;
        tie(l, r, k, x, y) = qry[qr];
        int _l = ceil(1.0 * (l - t) / k), _r = floor(1.0 * (r - t) / k);
        ans[qr] = min(ans[qr], rmq(_l, _r));
      }
    }
  }
  for (int i = 1; i <= q; i++) cout << (ans[i] > n ? -1 : ord[ans[i]]) << " ";
  return 0;
}
