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 = 100100, M = 200200;
int i, j, k, t, n, m, q, ch, l, r, ll, rr, S = 80;
int a[N], rk[N], lg2[N], ans[N];
char s1[N], s2[N];
struct dd {
  int l, r, k, x, y, q;
} Q[N];
int min(const int &x, const int &y) {
  if (x < y) return x;
  return y;
}
void R(int &x) {
  x = 0;
  ch = getchar();
  while (ch < '0' || '9' < ch) ch = getchar();
  while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
void W(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) W(x / 10);
  putchar(x % 10 + '0');
}
struct SA {
  int i, j, k, n, m, nn;
  int s[M], nm[M], x[M], y[M], sa[M], rk[M], ht[M], ST[M][22];
  void work() {
    m = 26;
    for (i = 1; i <= m; i++) nm[i] = 0;
    for (i = 1; i <= n; i++) x[i] = s[i], nm[s[i]]++;
    for (i = 1; i <= m; i++) nm[i] += nm[i - 1];
    for (i = n; i; i--) sa[nm[x[i]]--] = i;
    for (k = 1; k <= n; k <<= 1) {
      nn = 0;
      for (i = n - k + 1; i <= n; i++) y[++nn] = i;
      for (i = 1; i <= n; i++)
        if (sa[i] > k) y[++nn] = sa[i] - k;
      for (i = 1; i <= m; i++) nm[i] = 0;
      for (i = 1; i <= n; i++) nm[x[i]]++;
      for (i = 1; i <= m; i++) nm[i] += nm[i - 1];
      for (i = n; i; i--) sa[nm[x[y[i]]]--] = y[i];
      m = 1;
      y[sa[1]] = 1;
      for (i = 2; i <= n; i++) {
        if (x[sa[i - 1]] == x[sa[i]] && sa[i - 1] + k <= n && sa[i] + k <= n &&
            x[sa[i - 1] + k] == x[sa[i] + k])
          y[sa[i]] = m;
        else
          y[sa[i]] = ++m;
      }
      if (m >= n) break;
      for (i = 1; i <= n; i++) x[i] = y[i];
    }
    for (i = 1; i <= n; i++) rk[sa[i]] = i;
    k = 0;
    for (i = 1; i <= n; i++) {
      if (k) k--;
      if (rk[i] == 1) continue;
      j = sa[rk[i] - 1];
      while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
      ht[i] = k;
      ST[rk[i]][0] = k;
    }
    nn = 0;
    while ((1 << nn) < n) nn++;
    for (j = 1; j <= nn; j++)
      for (i = 1; i <= n; i++)
        if (i + (1 << j) - 1 <= n)
          ST[i][j] = min(ST[i][j - 1], ST[i + (1 << j - 1)][j - 1]);
  }
  int lcp(int a, int b) {
    if (a == b) return n - a + 1;
    int t;
    a = rk[a];
    b = rk[b];
    if (a > b) {
      t = a;
      a = b;
      b = t;
    }
    a++;
    t = lg2[b - a + 1];
    return min(ST[a][t], ST[b - (1 << t) + 1][t]);
  }
} A;
struct cc {
  int i, j, k, n, nn;
  int a[N], ST[N][22];
  void work() {
    nn = 0;
    while ((1 << nn) < n) nn++;
    for (i = 0; i <= n; i++) ST[i][0] = a[i];
    for (j = 1; j <= nn; j++)
      for (i = 0; i <= n; i++)
        if (i + (1 << j) - 1 <= n) {
          if (rk[ST[i][j - 1]] < rk[ST[i + (1 << j - 1)][j - 1]])
            ST[i][j] = ST[i][j - 1];
          else
            ST[i][j] = ST[i + (1 << j - 1)][j - 1];
        }
  }
  int get_min(int l, int r) {
    int t = lg2[r - l + 1];
    if (rk[ST[l][t]] < rk[ST[r - (1 << t) + 1][t]]) return ST[l][t];
    return ST[r - (1 << t) + 1][t];
  }
} B;
bool cmp(const int &a, const int &b) {
  int t;
  if (a < b) {
    if (b - a >= m) {
      t = A.lcp(n + 1, a + 1);
      if (t < m) return A.s[n + t + 1] < A.s[a + t + 1];
      t = A.lcp(a + 1, a + m + 1);
      if (t < b - a - m) return A.s[a + t + 1] < A.s[a + m + t + 1];
      t = A.lcp(b - m + 1, n + 1);
      if (t < m) return A.s[b - m + t + 1] < A.s[n + t + 1];
      return a < b;
    }
    t = A.lcp(n + 1, a + 1);
    if (t < b - a) return A.s[n + t + 1] < A.s[a + t + 1];
    t = A.lcp(n + b - a + 1, n + 1);
    if (t < m - (b - a)) return A.s[n + b - a + t + 1] < A.s[n + t + 1];
    t = A.lcp(a + 1, n + m - (b - a) + 1);
    if (t < b - a) return A.s[a + t + 1] < A.s[n + m - (b - a) + t + 1];
    return a < b;
  }
  if (a - b >= m) {
    t = A.lcp(b + 1, n + 1);
    if (t < m) return A.s[b + t + 1] < A.s[n + t + 1];
    t = A.lcp(b + m + 1, b + 1);
    if (t < a - b - m) return A.s[b + m + t + 1] < A.s[b + t + 1];
    t = A.lcp(n + 1, a - m + 1);
    if (t < m) return A.s[n + t + 1] < A.s[a - m + t + 1];
    return a < b;
  }
  t = A.lcp(b + 1, n + 1);
  if (t < a - b) return A.s[b + t + 1] < A.s[n + t + 1];
  t = A.lcp(n + 1, n + a - b + 1);
  if (t < m - (a - b)) return A.s[n + t + 1] < A.s[n + a - b + t + 1];
  t = A.lcp(n + m - (a - b) + 1, b + 1);
  if (t < a - b) return A.s[n + m - (a - b) + t + 1] < A.s[b + t + 1];
  return a < b;
}
bool cmp1(const dd &a, const dd &b) { return a.k < b.k; }
int main() {
  scanf("%s%s", s1 + 1, s2 + 1);
  n = strlen(s1 + 1);
  m = strlen(s2 + 1);
  for (i = 0; (1 << i) <= n + m; i++) lg2[1 << i] = i;
  for (i = 3; i <= n + m; i++)
    if (!lg2[i]) lg2[i] = lg2[i - 1];
  for (i = 1; i <= n; i++) A.s[i] = s1[i] - 'a' + 1;
  for (i = 1; i <= m; i++) A.s[n + i] = s2[i] - 'a' + 1;
  A.n = n + m;
  A.work();
  for (i = 0; i <= n; i++) a[i] = i;
  sort(a, a + n + 1, cmp);
  for (i = 0; i <= n; i++) rk[a[i]] = i;
  while (S * S > n) S--;
  R(q);
  for (i = 1; i <= q; i++) {
    R(Q[i].l);
    R(Q[i].r);
    R(Q[i].k);
    R(Q[i].x);
    R(Q[i].y);
    Q[i].q = i;
    ans[i] = -1;
  }
  sort(Q + 1, Q + q + 1, cmp1);
  l = 1;
  r = 0;
  for (i = 1; i <= S; i++) {
    while (l <= q && Q[l].k < i) l++;
    if (Q[l].k != i) continue;
    r = l;
    while (Q[r + 1].k == i) r++;
    for (j = 0; j < i; j++) {
      for (k = l; k <= r; k++)
        if (Q[k].x <= j && j <= Q[k].y) break;
      if (k > r) continue;
      B.n = -1;
      for (k = j; k <= n; k += i) B.a[++B.n] = k;
      B.work();
      for (k = l; k <= r; k++)
        if (Q[k].x <= j && j <= Q[k].y) {
          if (Q[k].l % i <= j)
            ll = Q[k].l / i;
          else
            ll = Q[k].l / i + 1;
          if (Q[k].r % i >= j)
            rr = Q[k].r / i;
          else
            rr = Q[k].r / i - 1;
          if (ll > rr) continue;
          t = B.get_min(ll, rr);
          if (ans[Q[k].q] == -1 || rk[t] < rk[ans[Q[k].q]]) ans[Q[k].q] = t;
        }
    }
  }
  B.n = n;
  for (i = 0; i <= n; i++) B.a[i] = i;
  B.work();
  for (i = r + 1; i <= q; i++) {
    for (j = 0; j <= n; j += Q[i].k) {
      ll = j + Q[i].x;
      rr = j + Q[i].y;
      rr = min(rr, Q[i].r);
      ll = max(ll, Q[i].l);
      if (ll > rr) continue;
      t = B.get_min(ll, rr);
      if (ans[Q[i].q] == -1 || rk[t] < rk[ans[Q[i].q]]) ans[Q[i].q] = t;
    }
  }
  for (i = 1; i <= q; i++) W(ans[i]), putchar(' ');
  puts("");
}
