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 = 4e5 + 10;
const int B = 2010;
char s[N], t[N];
int Q, n, m, id[N], rk[N], lg[N];
namespace Sub1 {
const int base = 233;
const int mod = 998244353;
int pw[N];
int hshs[N], hsht[N];
inline int getit(int i, int j) {
  if (j <= i)
    return s[j] - 'a';
  else if (j <= i + m)
    return t[j - i] - 'a';
  else
    return s[j - m] - 'a';
}
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; }
inline int mul(int p, int i) { return 1ll * p * pw[i] % mod; }
inline int gethsh(int i, int j) {
  if (j <= i)
    return hshs[j];
  else if (j <= i + m)
    return add(hsht[j - i], mul(hshs[i], j - i));
  else
    return add(add(mul(hshs[i], j - i), mul(hsht[m], j - m - i)),
               dec(hshs[j - m], mul(hshs[i], j - m - i)));
}
inline bool cmp(int x, int y) {
  int l = 0, r = n + m, ans = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (gethsh(x, mid) == gethsh(y, mid))
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  if (ans == n + m)
    return x < y;
  else
    return getit(x, ans + 1) < getit(y, ans + 1);
}
inline void init_hsh() {
  pw[0] = 1;
  for (int i = 1; i <= n + m; ++i) pw[i] = 1ll * base * pw[i - 1] % mod;
  hshs[0] = 0;
  for (int i = 1; i <= n; ++i)
    hshs[i] = add(mul(hshs[i - 1], 1), s[i] - 'a' + 1);
  hsht[0] = 0;
  for (int i = 1; i <= m; ++i)
    hsht[i] = add(mul(hsht[i - 1], 1), t[i] - 'a' + 1);
}
}  // namespace Sub1
using namespace Sub1;
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 read(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;
int ret[N];
struct query {
  int l, r, k, x, y, id;
} q[N];
vector<int> que[B];
inline int getmn(int x, int y) {
  if (x == -1 || y == -1) return x + y + 1;
  return rk[x] < rk[y] ? x : y;
}
struct RMQ {
  int st[N][25];
  inline void fill(int tp) {
    for (int i = 0; i <= n; ++i) st[i][0] = tp ? i : -1;
  }
  inline void init(int t = n) {
    for (int j = 1; j <= lg[t + 1]; ++j)
      for (int i = 0; i + (1 << j) - 1 <= t; ++i)
        st[i][j] = getmn(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  }
  inline int que(int l, int r) {
    if (l > r) return -1;
    int k = lg[r - l + 1];
    return getmn(st[l][k], st[r - (1 << k) + 1][k]);
  }
} R1, R2;
int main() {
  scanf("%s", s + 1);
  scanf("%s", t + 1);
  read(Q);
  n = strlen(s + 1);
  m = strlen(t + 1);
  init_hsh();
  for (int i = 2; i <= n + 5; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 0; i <= n; ++i) id[i] = i;
  sort(id, id + n + 1, cmp);
  for (int i = 0; i <= n; ++i) rk[id[i]] = i;
  int bl = 88;
  R1.fill(1);
  R1.init();
  for (int i = 1; i <= Q; ++i) {
    read(q[i].l);
    read(q[i].r);
    read(q[i].k);
    read(q[i].x);
    read(q[i].y);
    int l = q[i].l, r = q[i].r, k = q[i].k, x = q[i].x, y = q[i].y;
    if (k <= bl) {
      que[k].push_back(i);
      ret[i] = -1;
      continue;
    }
    int pos = -1;
    x += (l / k) * k, y += (l / k) * k;
    for (; x <= r; x += k, y += k) {
      int L = max(l, x), R = min(r, y);
      pos = getmn(pos, R1.que(L, R));
    }
    ret[i] = pos;
  }
  R2.fill(0);
  for (int k = 1; k <= min(bl, n); ++k) {
    for (int r = 0; r < k; ++r) {
      int j = 0;
      for (int i = r; i <= n; i += k, ++j) R2.st[j][0] = i;
      R2.init(j - 1);
      for (int i : que[k]) {
        if (q[i].x <= r && r <= q[i].y) {
          int p = q[i].l % k, z = q[i].r % k;
          int L = (p > r) ? (q[i].l / k + 1) : q[i].l / k,
              R = (z >= r) ? (q[i].r / k) : (q[i].r / k - 1);
          ret[i] = getmn(ret[i], R2.que(L, R));
        }
      }
    }
  }
  for (int i = 1; i <= Q; ++i) putint(ret[i], ' ');
  flush();
  return 0;
}
