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>
#pragma optimize("Ofast")
const int maxn = 2E+5 + 5;
int n, m, lg[maxn];
char str[maxn], *S, *T;
namespace Sub1 {
int ST[18][maxn];
namespace SA {
int n, m, x[maxn], y[maxn], c[maxn];
int hei[maxn], rk[maxn], sa[maxn];
inline void SA() {
  m = 122, n = ::n + ::m;
  for (int i = 1; i <= n; ++i) x[i] = str[i], ++c[x[i]];
  for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int num = 0;
    for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > k) y[++num] = sa[i] - k;
    for (int i = 1; i <= m; ++i) c[i] = 0;
    for (int i = 1; i <= n; ++i) ++c[x[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
    std::swap(x, y);
    num = 1, x[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
        x[sa[i]] = num;
      else
        x[sa[i]] = ++num;
    }
    if (num == n) break;
    m = num;
  }
  int k = 0;
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (rk[i] == 1) continue;
    if (k) --k;
    int j = sa[rk[i] - 1];
    while (i + k <= n && j + k <= n && str[i + k] == str[j + k]) ++k;
    hei[rk[i]] = k;
  }
}
inline void getST() {
  for (int i = 1; i <= n; ++i) ST[0][i] = hei[i];
  int Len = log2(n);
  for (int len = 1; len <= Len; ++len)
    for (int i = 1; i <= n; ++i) {
      ST[len][i] = ST[len - 1][i];
      if (i + (1 << len - 1) <= n)
        ST[len][i] = std::min(ST[len][i], ST[len - 1][i + (1 << len - 1)]);
    }
  lg[0] = -1;
  for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}
}  // namespace SA
inline int lcp(int x, int y) {
  x = SA::rk[x], y = SA::rk[y];
  if (x > y) std::swap(x, y);
  ++x;
  int len = log2(y - x + 1);
  int res = std::min(ST[len][x], ST[len][y - (1 << len) + 1]);
  return res;
}
inline bool cmp(int i, int j) {
  if (i == j) return 1;
  bool f = 0;
  if (i > j) std::swap(i, j), f = 1;
  int p = j - i, k = std::min(p, m), l = lcp(n + 1, i + 1);
  if (l < k) return f ^ (T[l + 1] < S[i + l + 1]);
  if (p < m) {
    int t = m - p;
    l = lcp(n + m - t + 1, n + 1);
    if (l < t) return f ^ (T[m - t + 1 + l] < T[l + 1]);
  }
  if (p > m) {
    int t = p - m;
    l = lcp(i + 1, j - t + 1);
    if (l < t) return f ^ (S[i + l + 1] < S[j - t + 1 + l]);
  }
  l = lcp(j - k + 1, n + m - k + 1);
  if (l < k) return f ^ (S[j - k + 1 + l] < T[m - k + 1 + l]);
  return !f;
}
}  // namespace Sub1
inline int getint(int x = 0) {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
int s[32], t;
inline void putint(int x = 0, char suf = ' ') {
  if (!x) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  while (x) s[++t] = x % 10, x /= 10;
  while (t) putchar(s[t--] + '0');
  putchar(suf);
}
namespace Sub2 {
const int B = 88;
int q, p[maxn], pp[maxn], cnt, ans[maxn];
struct Query {
  int l, r, k, x, y, id;
} qry[maxn];
namespace Sub3 {
int h[maxn];
std::vector<std::pair<int, int>> st[B][17];
inline void getST(std::vector<std::pair<int, int>> *st, int n) {
  st[0].resize(n + 1), st[0].shrink_to_fit();
  for (int i = 0; i <= n; ++i) st[0][i] = std::make_pair(h[i], i);
  int Len = lg[n + 1];
  for (int len = 1; len <= Len; ++len) {
    st[len].resize(n + 1), st[len].shrink_to_fit();
    for (int i = 0; i <= n; ++i) {
      st[len][i] = st[len - 1][i];
      if (i + (1 << len - 1) <= n)
        st[len][i] = std::min(st[len][i], st[len - 1][i + (1 << len - 1)]);
    }
  }
}
inline std::pair<int, int> ST(std::vector<std::pair<int, int>> *st, int l,
                              int r) {
  int len = lg[r - l + 1];
  std::pair<int, int> res = std::min(st[len][l], st[len][r - (1 << len) + 1]);
  return res;
}
void main() {
  std::sort(qry + 1, qry + cnt + 1, [](Query x, Query y) { return x.k < y.k; });
  for (int i = 1, k = -1; i <= cnt; ++i) {
    if (qry[i].k != k) {
      k = qry[i].k;
      for (int t = 0; t < k; ++t) {
        for (int l = t; l <= n; l += k) h[l / k] = pp[l];
        getST(st[t], (n - t) / k);
      }
    }
    for (int t = qry[i].x; t <= qry[i].y; ++t) {
      int L = ceil(1.0 * (qry[i].l - t) / k);
      int R = floor(1.0 * (qry[i].r - t) / k);
      if (L <= R) {
        auto o = ST(st[t], L, R);
        if (!~ans[qry[i].id] || pp[ans[qry[i].id]] > pp[o.second * k + t])
          ans[qry[i].id] = o.second * k + t;
      }
    }
  }
}
}  // namespace Sub3
std::pair<int, int> st[maxn][17];
inline void getST() {
  for (int i = 0; i <= n; ++i) st[i][0] = std::make_pair(pp[i], i);
  int Len = lg[n + 1];
  for (int len = 1; len <= Len; ++len)
    for (int i = 0; i <= n; ++i) {
      st[i][len] = st[i][len - 1];
      if (i + (1 << len - 1) <= n)
        st[i][len] = std::min(st[i][len], st[i + (1 << len - 1)][len - 1]);
    }
}
inline std::pair<int, int> ST(int l, int r) {
  int len = lg[r - l + 1];
  std::pair<int, int> res = std::min(st[l][len], st[r - (1 << len) + 1][len]);
  return res;
}
void main() {
  for (int i = 0; i <= n; ++i) p[i] = i;
  std::sort(p, p + n + 1, Sub1::cmp);
  for (int i = 0; i <= n; ++i) pp[p[i]] = i;
  getST(), q = getint();
  for (int i = 1; i <= q; ++i) {
    int l = getint(), r = getint(), k = getint(), x = getint(), y = getint();
    ans[i] = -1;
    if (k >= B || (r - l + 1) / k <= n / 100) {
      for (int t = 0; t * k <= n; ++t) {
        int L = t * k + x, R = t * k + y;
        if (!(L <= r && R >= l)) continue;
        L = std::max(L, l), R = std::min(R, r);
        auto o = ST(L, R);
        if (!~ans[i] || pp[ans[i]] > o.first) ans[i] = o.second;
      }
    } else
      qry[++cnt] = {l, r, k, x, y, i};
  }
  Sub3::main();
  for (int i = 1; i <= q; ++i) putint(ans[i]);
}
}  // namespace Sub2
int main() {
  scanf("%s", str + 1), n = strlen(str + 1), S = str;
  scanf("%s", str + n + 1), m = strlen(str + n + 1), T = str + n;
  Sub1::SA::SA(), Sub1::SA::getST(), Sub2::main();
}
