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;
struct ii {
  int x, y;
  ii(int x = 0, int y = 0) : x(x), y(y) {}
  bool operator<(const ii &a) const {
    if (x != a.x) return x < a.x;
    return y < a.y;
  }
  bool operator==(const ii &a) const { return x == a.x && y == a.y; }
  ii friend operator+(ii a, ii b) { return ii(a.x + b.x, a.y + b.y); }
  ii friend operator-(ii a, ii b) { return ii(a.x - b.x, a.y - b.y); }
};
template <class T>
void sc(T &x) {
  x = 0;
  char c;
  int f = 1;
  while (c = getchar(), c < 48)
    if (c == '-') f = -1;
  do x = x * 10 + (c ^ 48);
  while (c = getchar(), c > 47);
  x *= f;
}
template <class T>
void nt(T x) {
  if (!x) return;
  nt(x / 10);
  putchar(x % 10 + '0');
}
template <class T>
void pt(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (!x)
    putchar('0');
  else
    nt(x);
}
template <class T>
void pts(T x) {
  pt(x);
  putchar(' ');
}
template <class T>
void ptn(T x) {
  pt(x);
  putchar('\n');
}
template <class v>
void pp(v x, int y) {
  static char ch[] = {" \n"};
  pt(x);
  putchar(ch[y]);
}
template <class T>
void PP(T *x, int y) {
  for (int i = 0, i_ = y; i < i_; ++i) pp(x[i], i == y - 1);
}
template <class T>
void Max(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
void Min(T &x, T y) {
  if (x > y) x = y;
}
const int maxn = 200005;
const int maxb = 505;
char s[maxn];
int n;
int A, B;
int rk[maxn], sa[maxn], h[maxn], c[maxn];
int mn[18][maxn], sp[maxn];
void SAbuild() {
  for (int i = 1, i_ = n + 1; i < i_; ++i) rk[i] = s[i] - 'a' + 1, c[rk[i]]++;
  for (int i = 1, i_ = 'z'; i < i_; ++i) c[i] += c[i - 1];
  for (int i = 1, i_ = n + 1; i < i_; ++i) sa[c[rk[i]]--] = i;
  int *x = rk, *y = h;
  for (int m = 1; m < n; m <<= 1) {
    int p = 0;
    for (int i = n - m + 1, i_ = n + 1; i < i_; ++i) y[p++] = i;
    for (int i = 1, i_ = n + 1; i < i_; ++i)
      if (sa[i] > m) y[p++] = sa[i] - m;
    for (int i = 1, i_ = n + 1; i < i_; ++i) c[x[sa[i]]] = i;
    for (int i = (p)-1, i_ = 0; i >= i_; --i) sa[c[x[y[i]]]--] = y[i];
    p = 0;
    for (int i = 1, i_ = n + 1; i < i_; ++i) {
      if (x[sa[i]] != x[sa[i - 1]] || x[sa[i] + m] != x[sa[i - 1] + m]) p++;
      y[sa[i]] = p;
    }
    swap(x, y);
    if (p == n) break;
  }
  if (x != rk) memcpy(rk, x, sizeof rk);
  memset(h, 0, sizeof h);
  {
    int k = 0;
    for (int i = 1, i_ = n + 1; i < i_; ++i) {
      if (k) k--;
      for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++)
        ;
      h[rk[i]] = k;
    }
  }
  for (int i = 2, i_ = n + 1; i < i_; ++i) sp[i] = sp[i >> 1] + 1;
  for (int i = 2, i_ = n + 1; i < i_; ++i) mn[0][i] = h[i];
  for (int i = 1, i_ = sp[n] + 1; i < i_; ++i)
    for (int j = 1, j_ = n - (1 << i) + 2; j < j_; ++j) {
      mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
    }
}
int get(int x, int y) {
  if (x == y) return (1 << 30);
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  x++;
  int k = sp[y - x + 1];
  return min(mn[k][x], mn[k][y - (1 << k) + 1]);
}
bool cmp(int i, int j) {
  bool chg = 0;
  if (i < j) swap(i, j), chg = 1;
  if (j + B > i) {
    int a = get(j + 1, A + 1);
    if (a < i - j) return chg ^ (s[j + 1 + a] < s[A + 1 + a]);
    a = get(A + 1, A + i - j + 1);
    if (a < B - i + j) return chg ^ (s[A + 1 + a] < s[A + 1 + i - j + a]);
    a = get(A + j + B - i + 1, j + 1);
    if (a < i - j) return chg ^ (s[A + 1 + j + B - i + a] < s[j + 1 + a]);
  } else {
    int a = get(j + 1, A + 1);
    if (a < B) return chg ^ (s[1 + j + a] < s[1 + A + a]);
    a = get(j + B + 1, j + 1);
    if (a < i - j - B) return chg ^ (s[1 + j + B + a] < s[1 + j + a]);
    a = get(A + 1, i - B + 1);
    if (a < B) return chg ^ (s[1 + A + a] < s[1 - B + i + a]);
  }
  return chg ^ (i < j);
}
int dat[maxn];
int ans[maxn];
int rs[18][maxn];
int qry(int l, int r) {
  int k = sp[r - l + 1];
  return min(rs[k][l], rs[k][r - (1 << k) + 1]);
}
struct abcd {
  int l, r, k, x, y, id;
  bool operator<(const abcd &a) const { return k < a.k; }
};
vector<abcd> g;
long long d[maxn];
int solve(int l, int r, int k, int x, int y) {
  int R = l / k * k + y;
  if (R < l) R += k;
  int L = R - (y - x);
  int ans = (1 << 30);
  while (L <= r) {
    Min(ans, qry(max(l, L), min(r, R)));
    L += k;
    R += k;
  }
  if (ans == (1 << 30))
    return -1;
  else
    return dat[ans];
}
int main() {
  scanf("%s", s + 1);
  A = strlen(s + 1);
  scanf("%s", s + A + 1);
  B = strlen(s + A + 1);
  n = A + B;
  SAbuild();
  int Q;
  sc(Q);
  for (int i = 1, i_ = A + 1; i < i_; ++i) dat[i] = i;
  sort(dat, dat + A + 1, cmp);
  for (int i = 0, i_ = A + 1; i < i_; ++i) rk[dat[i]] = i;
  n = A;
  for (int i = 0, i_ = n + 1; i < i_; ++i) rs[0][i] = rk[i];
  for (int i = 1, i_ = sp[n + 1] + 1; i < i_; ++i)
    for (int j = 0, j_ = n - (1 << i) + 2; j < j_; ++j) {
      rs[i][j] = min(rs[i - 1][j], rs[i - 1][j + (1 << (i - 1))]);
    }
  for (int i = 0, i_ = Q; i < i_; ++i) {
    int l, r, k, x, y;
    sc(l);
    sc(r);
    sc(k);
    sc(x);
    sc(y);
    if (k > maxb)
      ans[i] = solve(l, r, k, x, y);
    else
      g.push_back((abcd){l, r, k, x, y, i}), d[k] += (r - l) / k + 1;
  }
  sort((g).begin(), (g).end());
  for (int i = 0, i_ = (int)(g).size(); i < i_; ++i) {
    int k = g[i].k;
    if (d[k] <= maxb) ans[g[i].id] = solve(g[i].l, g[i].r, k, g[i].x, g[i].y);
  }
  for (int i = 0, j = 0; i < (int)(g).size(); i = j) {
    for (; g[j].k == g[i].k; j++)
      ;
    int k = g[i].k;
    if (d[k] <= maxb) continue;
    for (int t = i, t_ = j; t < t_; ++t) ans[g[t].id] = (1 << 30);
    for (int s = 0, s_ = g[i].k; s < s_; ++s) {
      int nn = n / k;
      for (int i = 0, i_ = nn + 1; i < i_; ++i) rs[0][i] = rk[i * k + s];
      for (int i = 1, i_ = sp[nn + 1] + 1; i < i_; ++i)
        for (int j = 0, j_ = nn - (1 << i) + 2; j < j_; ++j) {
          rs[i][j] = min(rs[i - 1][j], rs[i - 1][j + (1 << (i - 1))]);
        }
      for (int t = i, t_ = j; t < t_; ++t)
        if (g[t].x <= s && g[t].y >= s) {
          int l = g[t].l / k;
          if (l * k + s < g[t].l) l++;
          int r = g[t].r / k;
          if (r * k + s > g[t].r) r--;
          if (l <= r) Min(ans[g[t].id], qry(l, r));
        }
    }
    for (int t = i, t_ = j; t < t_; ++t) {
      if (ans[g[t].id] == (1 << 30))
        ans[g[t].id] = -1;
      else
        ans[g[t].id] = dat[ans[g[t].id]];
    }
  }
  for (int i = 0, i_ = Q; i < i_; ++i) pts(ans[i]);
  return 0;
}
