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 = 100010, SZ = 88;
const int P = 998244353, B = 233;
int n, m, q, rk[maxn], hs[maxn], ht[maxn], pw[maxn];
int st[17][maxn], lg[maxn], ans[maxn], mp[maxn];
char s[maxn], t[maxn];
vector<tuple<int, int, int>> Q[SZ + 5][SZ + 5];
int main() {
  scanf("%s %s %d", s + 1, t + 1, &q);
  n = strlen(s + 1), m = strlen(t + 1);
  for (int i = pw[0] = 1; i <= max(n, m); i++) {
    pw[i] = 1LL * pw[i - 1] * B % P;
    if (i > 1) lg[i] = lg[i >> 1] + 1;
  }
  for (int i = 1; i <= n; i++) {
    hs[i] = (1LL * hs[i - 1] * B + s[i]) % P;
  }
  for (int i = 1; i <= m; i++) {
    ht[i] = (1LL * ht[i - 1] * B + t[i]) % P;
  }
  auto substr = [&](int p, int k) {
    if (k <= p) return hs[k];
    if (k <= p + m) return int((1LL * hs[p] * pw[k - p] + ht[k - p]) % P);
    return int((1LL * hs[p] * pw[k - p] + 1LL * ht[m] * pw[k - p - m] +
                hs[k - m] - 1LL * hs[p] * pw[k - m - p] % P + P) %
               P);
  };
  auto lcp = [&](int x, int y) {
    int l = 1, r = n + m + 1, ans = 0;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (substr(x, mid) == substr(y, mid))
        l = (ans = mid) + 1;
      else
        r = mid - 1;
    }
    return ans;
  };
  auto get_pos = [&](int p, int k) {
    if (k <= p) return s[k];
    return k <= p + m ? t[k - p] : s[k - m];
  };
  iota(rk, rk + n + 1, 0);
  stable_sort(rk, rk + n + 1, [&](int x, int y) {
    int l = lcp(x, y);
    return get_pos(x, l + 1) < get_pos(y, l + 1);
  });
  auto init = [&](int n) {
    for (int i = 1; i < 17; i++) {
      for (int j = 0; j + (1 << i) - 1 <= n; j++) {
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
  };
  auto query = [&](int l, int r) {
    if (l > r) return n + 1;
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
  };
  for (int i = 0; i <= n; i++) {
    st[0][rk[i]] = mp[rk[i]] = i;
  }
  init(n);
  for (int i = 1, l, r, k, x, y; i <= q; i++) {
    scanf("%d %d %d %d %d", &l, &r, &k, &x, &y), ans[i] = n + 1;
    if (k > SZ) {
      for (; x <= n; x += k, y += k) {
        ans[i] = min(ans[i], query(max(x, l), min(y, r)));
      }
    } else {
      for (int j = x; j <= y; j++) {
        Q[k][j].emplace_back(l, r, i);
      }
    }
  }
  for (int i = 1; i <= SZ; i++) {
    for (int j = 0; j < i; j++) {
      int m = -1;
      for (int k = j; k <= n; k += i) st[0][++m] = mp[k];
      init(m);
      for (auto p : Q[i][j])
        if (get<1>(p) >= j) {
          int l = (get<0>(p) - j + i - 1) / i, r = (get<1>(p) - j) / i;
          ans[get<2>(p)] = min(ans[get<2>(p)], query(l, r));
        }
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d ", ans[i] > n ? -1 : rk[ans[i]]);
  }
  return 0;
}
