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;
namespace iobuff {
const int LEN = 1000000;
char in[LEN + 5], out[LEN + 5];
char *pin = in, *pout = out, *ed = in, *eout = out + LEN;
inline char gc(void) {
  return pin == ed && (ed = (pin = in) + fread(in, 1, LEN, stdin), ed == in)
             ? EOF
             : *pin++;
}
inline void pc(char c) {
  pout == eout && (fwrite(out, 1, LEN, stdout), pout = out);
  (*pout++) = c;
}
inline void flush() { fwrite(out, 1, pout - out, stdout), pout = out; }
template <typename T>
inline void scan(T &x) {
  static int f;
  static char c;
  c = gc(), f = 1, x = 0;
  while (c < '0' || c > '9') f = (c == '-' ? -1 : 1), c = gc();
  while (c >= '0' && c <= '9') x = 10 * x + c - '0', c = gc();
  x *= f;
}
template <typename T>
inline void putint(T x, char div) {
  static char s[15];
  static int top;
  top = 0;
  x < 0 ? pc('-'), x = -x : 0;
  while (x) s[top++] = x % 10, x /= 10;
  !top ? pc('0'), 0 : 0;
  while (top--) pc(s[top] + '0');
  pc(div);
}
}  // namespace iobuff
using namespace iobuff;
const int N = 2e5 + 10;
char S[N], T[N];
const int base = 233, mod = 998244353;
inline int add(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; }
inline int dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; }
int hshs[N], hsht[N], Pow[N], ret;
int id[N], rk[N];
int n, m, Q, Log2[N];
inline void init() {
  Pow[0] = 1;
  for (int i = 1; i <= max(n, m); ++i) Pow[i] = 1ll * Pow[i - 1] * base % mod;
  for (int i = 1; i <= n; ++i)
    hshs[i] = add((1ll * base * hshs[i - 1] % mod), (S[i] - 'a'));
  for (int i = 1; i <= m; ++i)
    hsht[i] = add((1ll * base * hsht[i - 1] % mod), (T[i] - 'a'));
  for (int i = 2; i <= n + 5; ++i) Log2[i] = Log2[i >> 1] + 1;
}
int L;
inline int gethsh(int pos, int len) {
  ret = 0;
  if (pos > L) {
    if (len <= pos - L)
      return dec(hshs[L + len - 1], 1ll * hshs[L - 1] * Pow[len] % mod);
    ret = dec(hshs[pos - 1], 1ll * hshs[L - 1] * Pow[pos - L] % mod),
    len -= pos - L;
  }
  if (len <= m)
    ret = add(1ll * ret * Pow[len] % mod, hsht[len]);
  else {
    ret = add(1ll * ret * Pow[m] % mod, hsht[m]);
    len -= m;
    ret = add(1ll * ret * Pow[len] % mod,
              dec(hshs[pos + len - 1], 1ll * hshs[pos - 1] * Pow[len] % mod));
  }
  return ret;
}
inline int binary(int pos1, int pos2) {
  int l = 1, r = m + n - L + 1, mid, ret = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (gethsh(pos2, mid) == gethsh(pos1, mid))
      l = mid + 1, ret = mid;
    else
      r = mid - 1;
  }
  return ret;
}
inline char getc(int x, int len) {
  if (x > L) {
    if (len <= x - L)
      return S[L + len - 1];
    else
      len -= x - L;
  }
  if (len <= m)
    return T[len];
  else
    len -= m;
  return S[x + len - 1];
}
inline bool cmp(int x, int y) {
  ++x;
  ++y;
  L = min(x, y);
  int len = binary(x, y);
  if (len == m + n - L + 1) return x < y;
  return getc(x, len + 1) < getc(y, len + 1);
}
inline int getmn(int x, int y) {
  if (x < 0) return y;
  if (y < 0) return x;
  return rk[x] < rk[y] ? x : y;
}
int st[N][21], tot, B;
struct Query {
  int l, r, k, x, y, ans;
} q[N];
vector<int> buc[N];
inline void build(int mod, int rem) {
  tot = 0;
  for (int i = rem; i <= n; i += mod) st[tot++][0] = i;
  for (int i = 1; i <= Log2[tot]; ++i)
    for (int j = 0; j + (1 << i) - 1 < tot; ++j)
      st[j][i] = getmn(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}
inline int query(int l, int r) {
  if (l > r) return -1;
  int len = Log2[r - l + 1];
  return getmn(st[l][len], st[r - (1 << len) + 1][len]);
}
inline int calc_floor(int x, int mod, int rem) {
  if (x % mod > rem)
    return x / mod + 1;
  else
    return x / mod;
}
inline int calc_ceil(int x, int mod, int rem) {
  if (x % mod >= rem)
    return x / mod;
  else
    return x / mod - 1;
}
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  scanf("%s", T + 1);
  m = strlen(T + 1);
  init();
  for (int i = 0; i <= n; ++i) id[i] = i;
  sort(id, id + 1 + n, cmp);
  for (int i = 0; i <= n; ++i) rk[id[i]] = i;
  scan(Q);
  int l, r, k, x, y;
  B = 88;
  build(1, 0);
  for (int i = 1; i <= Q; ++i) {
    scan(l);
    scan(r);
    scan(k);
    scan(x);
    scan(y);
    q[i] = (Query){l, r, k, x, y, -1};
    if (k <= B)
      buc[k].push_back(i);
    else {
      int b = l / k;
      x += b * k;
      y += b * k;
      for (; x <= r; x += k, y += k) {
        int L = max(l, x), R = min(r, y);
        q[i].ans = getmn(q[i].ans, query(L, R));
      }
    }
  }
  for (int o = 1; o <= min(B, n); ++o) {
    if (!buc[o].size()) continue;
    k = o;
    for (int i = 0; i < k; ++i) {
      build(k, i);
      for (int jj = 0, j; jj < buc[o].size(); ++jj) {
        j = buc[o][jj];
        if (i < q[j].x || i > q[j].y) continue;
        q[j].ans = getmn(
            q[j].ans, query(calc_floor(q[j].l, k, i), calc_ceil(q[j].r, k, i)));
      }
    }
  }
  for (int i = 1; i <= Q; ++i) putint(q[i].ans, ' ');
  flush();
  return 0;
}
