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 N = 1e5 + 5, K = 305, bas = 113, inf = 0x3f3f3f3f, mod = 1e9 + 7;
inline int add(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }
inline int dec(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
char s[N], t[N];
int p[N], n, m, rk[N], blk[N], lb[N], rb[N];
unsigned long long sh[N], th[N], pww[N];
namespace io {
inline int read(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 io
using io::putint;
using io::read;
inline unsigned long long ghsh(int l, int r, bool tp) {
  return tp ? dec(th[r], th[l - 1] * pww[r - l + 1] % mod)
            : dec(sh[r], sh[l - 1] * pww[r - l + 1] % mod);
}
inline bool pd(int x, int y) {
  if (y - x <= m) {
    if (ghsh(1, y - x, 1) != ghsh(x + 1, y, 0)) {
      int l = 0, r = y - x + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(1, mid, 1) == ghsh(x + 1, x + mid, 0) ? l = mid : r = mid;
      }
      return t[l + 1] < s[x + l + 1];
    } else if (ghsh(y - x + 1, m, 1) != ghsh(1, m - y + x, 1)) {
      int l = 0, r = m - y + x + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(y - x + 1, y - x + mid, 1) == ghsh(1, mid, 1) ? l = mid : r = mid;
      }
      return t[l + y - x + 1] < t[l + 1];
    } else if (ghsh(x + 1, y, 0) != ghsh(m - y + x + 1, m, 1)) {
      int l = 0, r = y - x + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(x + 1, x + mid, 0) == ghsh(m - y + x + 1, m - y + x + mid, 1)
            ? l = mid
            : r = mid;
      }
      return s[x + 1 + l] < t[m - y + x + 1 + l];
    }
  } else {
    if (ghsh(1, m, 1) != ghsh(x + 1, x + m, 0)) {
      int l = 0, r = m + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(1, mid, 1) == ghsh(x + 1, x + mid, 0) ? l = mid : r = mid;
      }
      return t[l + 1] < s[x + l + 1];
    } else if (ghsh(x + 1, y - m, 0) != ghsh(x + m + 1, y, 0)) {
      int l = 0, r = y - x - m + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(x + 1, x + mid, 0) == ghsh(x + m + 1, x + m + mid, 0) ? l = mid
                                                                   : r = mid;
      }
      return s[l + x + 1] < s[l + x + m + 1];
    } else if (ghsh(y - m + 1, y, 0) != ghsh(1, m, 1)) {
      int l = 0, r = m + 1;
      for (; l + 1 < r;) {
        int mid = l + r >> 1;
        ghsh(y - m + 1, y - m + mid, 0) == ghsh(1, mid, 1) ? l = mid : r = mid;
      }
      return s[l + y - m + 1] < t[l + 1];
    }
  }
  return 1;
}
struct cmp {
  inline bool operator()(const int& x, const int& y) {
    if (x < y)
      return pd(x, y);
    else
      return !pd(y, x);
  }
};
int st[N][20], pw[20], lg[N], o, ans[N];
int w[N], tr, mn[N][20];
struct RMQ {
  int st[N][20];
  inline void pre(const int* a, int p) {
    for (int i = 0; i <= p; ++i) st[i][0] = a[i];
    for (int j = 1; j <= lg[p + 1]; ++j)
      for (int i = 0; i + pw[j] - 1 <= p; ++i)
        st[i][j] = min(st[i][j - 1], st[i + pw[j - 1]][j - 1]);
  }
  inline int query(int l, int r) {
    if (l > r) return inf;
    int len = lg[r - l + 1];
    return min(st[l][len], st[r - pw[len] + 1][len]);
  }
} A, B;
struct quy {
  int l, r, x, y, id;
};
vector<quy> q[K];
int main() {
  scanf("%s%s", s + 1, t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  for (int i = 1; i <= n; ++i)
    sh[i] = add(sh[i - 1] * bas % mod, s[i] - 'a' + 1);
  for (int i = 1; i <= m; ++i)
    th[i] = add(th[i - 1] * bas % mod, t[i] - 'a' + 1);
  pww[0] = 1;
  for (int i = 1; i <= max(n, m); ++i) pww[i] = pww[i - 1] * bas % mod;
  for (int i = 0; i <= n; ++i) p[i] = i;
  sort(p, p + n + 1, cmp());
  for (int i = 0; i <= n; ++i) rk[p[i]] = i;
  lg[1] = 0;
  for (int i = 2; i <= n + 1; ++i) lg[i] = lg[i >> 1] + 1;
  pw[0] = 1;
  for (int i = 1; i <= lg[n + 1]; ++i) pw[i] = pw[i - 1] << 1;
  A.pre(rk, n);
  o = 200;
  int qq = read();
  for (int i = 1; i <= qq; ++i) {
    int l = read(), r = read(), k = read(), x = read(), y = read();
    if (k >= o) {
      int ll = l / k * k, ret = inf;
      for (; ll <= r; ll += k)
        ret = min(ret, A.query(max(l, ll + x), min(r, ll + y)));
      ans[i] = ret;
    } else
      q[k].push_back({l, r, x, y, i}), ans[i] = inf;
  }
  for (int i = 1; i < o; ++i) {
    if (q[i].empty()) continue;
    for (int j = 0; j < i; ++j) {
      tr = 0;
      for (int k = j; k <= n; k += i) w[tr++] = rk[k];
      B.pre(w, tr - 1);
      for (quy u : q[i])
        if (u.x <= j && j <= u.y) {
          int nl = (u.l % i > j) ? u.l / i + 1 : u.l / i,
              nr = (u.r % i >= j) ? u.r / i : u.r / i - 1;
          ans[u.id] = min(ans[u.id], B.query(nl, nr));
        }
    }
  }
  for (int i = 1; i <= qq; ++i) putint(ans[i] >= inf ? -1 : p[ans[i]]);
  return 0;
}
