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;
int lg[200020];
namespace SA {
int n, sa[200020], rk[200020], xx[200020], yy[200020], t[200020],
    st[18][200020];
void getsa(char a[]) {
  int *x = xx, *y = yy, m = 200;
  for (int i = 1; i <= n; ++i) ++t[x[i] = a[i]];
  for (int i = 2; i <= m; ++i) t[i] += t[i - 1];
  for (int i = n; i; --i) sa[t[x[i]]--] = i;
  memset(t + 1, 0, m << 2);
  for (int len = 1;; len <<= 1) {
    int tot = 0;
    for (int i = n - len + 1; i <= n; ++i) y[++tot] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) y[++tot] = sa[i] - len;
    for (int i = 1; i <= n; ++i) ++t[x[i]];
    for (int i = 2; i <= m; ++i) t[i] += t[i - 1];
    for (int i = n; i; --i) sa[t[x[y[i]]]--] = y[i];
    memset(t + 1, 0, m << 2);
    swap(x, y);
    x[sa[1]] = 1, m = 1;
    for (int i = 2; i <= n; ++i)
      x[sa[i]] =
          y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]
              ? m
              : ++m;
    if (m == n) break;
  }
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1, k = 0; i <= n; ++i) {
    if (rk[i] == 1) continue;
    if (k) --k;
    while (a[i + k] == a[sa[rk[i] - 1] + k]) ++k;
    st[0][rk[i]] = k;
  }
  for (int i = 1; (1 << i) <= n; ++i)
    for (int j = 1; j <= n - (1 << i) + 1; ++j)
      st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
int qlcp(int x, int y) {
  if (x == y) return n - x + 1;
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  int len = lg[y - x];
  return min(st[len][x + 1], st[len][y - (1 << len) + 1]);
}
}  // namespace SA
const int siz = 300;
char s[200020], t[100010];
int n, m, qnum;
int rk[100010];
int p[100010];
struct query {
  int l, r, k, x, y, id;
  friend bool operator<(query a, query b) { return a.k < b.k; }
} q[100010];
int ans[100010];
void getrk() {
  for (int i = 0; i <= n; ++i) p[i] = i;
  sort(p, p + 1 + n, [&](int x, int y) {
    int f = 0;
    if (x > y) swap(x, y), f = 1;
    if (x + m <= y) {
      int l = SA::qlcp(n + 1, x + 1);
      if (l < m) return (s[n + l + 1] < s[x + l + 1]) ^ f;
      l = SA::qlcp(x + 1, x + m + 1);
      if (l < y - x - m) return (s[x + l + 1] < s[x + l + m + 1]) ^ f;
      l = SA::qlcp(y - m + 1, n + 1);
      if (l < m) return (s[y - m + 1 + l] < s[n + 1 + l]) ^ f;
      return (x < y) ^ f;
    } else {
      int l = SA::qlcp(n + 1, x + 1);
      if (l < y - x) return (s[n + 1 + l] < s[x + 1 + l]) ^ f;
      l = SA::qlcp(n + 1 + y - x, n + 1);
      if (l < m - (y - x)) return (s[n + 1 + y - x + l] < s[n + 1 + l]) ^ f;
      l = SA::qlcp(x + 1, n + m - (y - x) + 1);
      if (l < y - x) return (s[x + 1 + l] < s[n + m - (y - x) + 1 + l]) ^ f;
      return (x < y) ^ f;
    }
  });
  for (int i = 0; i <= n; ++i) rk[p[i]] = i;
}
struct Data {
  vector<vector<int> > st;
  void build(int n, int a[]) {
    st.resize(lg[n + 1] + 1);
    for (int i = 0; i <= lg[n + 1]; ++i) st[i].resize(n + 1);
    for (int i = 0; i <= n; ++i) st[0][i] = a[i];
    for (int i = 1; i <= lg[n + 1]; ++i)
      for (int j = 0; j <= n - (1 << i) + 1; ++j)
        st[i][j] = rk[st[i - 1][j]] <= rk[st[i - 1][j + (1 << (i - 1))]]
                       ? st[i - 1][j]
                       : st[i - 1][j + (1 << (i - 1))];
  }
  int query(int l, int r) {
    int len = lg[r - l + 1];
    return rk[st[len][l]] <= rk[st[len][r - (1 << len) + 1]]
               ? st[len][l]
               : st[len][r - (1 << len) + 1];
  }
} b[310];
int main() {
  for (int i = 2; i <= 200000; ++i) lg[i] = lg[i >> 1] + 1;
  scanf("%s %s %d", s + 1, t + 1, &qnum);
  n = strlen(s + 1), m = strlen(t + 1);
  SA::n = n + m;
  for (int i = 1; i <= m; ++i) s[i + n] = t[i];
  SA::getsa(s);
  getrk();
  for (int i = 0; i <= n; ++i) p[i] = i;
  for (int i = 1; i <= qnum; ++i) ans[i] = -1;
  for (int i = 1; i <= qnum; ++i)
    scanf("%d %d %d %d %d", &q[i].l, &q[i].r, &q[i].k, &q[i].x, &q[i].y),
        q[i].id = i;
  sort(q + 1, q + 1 + qnum);
  int last = 1;
  for (int k = 1; k <= siz; ++k) {
    for (int i = 0; i < k; ++i) {
      for (int j = 0; k * j + i <= n; ++j) p[j] = k * j + i;
      if (i <= n) b[i].build((n - i) / k, p);
    }
    while (q[last].k == k) {
      int x = q[last].x, y = q[last].y, l = q[last].l, r = q[last].r,
          id = q[last].id;
      for (int i = x; i <= y; ++i)
        if (i <= r) {
          int nl = (l - i + k - 1) / k, nr = (r - i) / k, cur;
          if (nl <= nr) {
            cur = b[i].query(nl, nr);
            if (ans[id] < 0 || rk[cur] < rk[ans[id]] ||
                (rk[cur] == rk[ans[id]] && cur < ans[id]))
              ans[id] = cur;
          }
        }
      ++last;
    }
  }
  for (int i = 0; i <= n; ++i) p[i] = i;
  b[0].build(n, p);
  while (last <= qnum) {
    int x = q[last].x, y = q[last].y, l = q[last].l, r = q[last].r,
        id = q[last].id, k = q[last].k;
    for (int i = 0; i <= n; i += k) {
      int nl = i + x, nr = i + y;
      if (nr < l || nl > r) continue;
      nl = max(nl, l);
      nr = min(nr, r);
      int cur = b[0].query(nl, nr);
      if (ans[id] < 0 || rk[cur] < rk[ans[id]] ||
          (rk[cur] == rk[ans[id]] && cur < ans[id]))
        ans[id] = cur;
    }
    ++last;
  }
  for (int i = 1; i <= qnum; ++i) printf("%d ", ans[i]);
  return 0;
}
