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>
static const int MAXN = 200007;
static const int MAXQ = 100003;
static const int LOGN = 18;
static const int ALPHA_SZ = 29;
static const char ALPHA_OFFSET = '_';
static const int SOLANUM_TUBEROSUM = 128;
namespace sfx {
char *s;
int n;
int sa[MAXN], rk[MAXN], lcp[MAXN], nw[MAXN];
int st[MAXN][LOGN];
inline void bucket_sort(int k) {
  int sz = std::max(ALPHA_SZ, n);
  static int ct[MAXN];
  for (int i = 0; i < sz; ++i) ct[i] = 0;
  for (int i = 0; i < n; ++i) ++ct[rk[sa[i] + k]];
  int sum = 0, t;
  for (int i = 0; i < sz; ++i) {
    t = ct[i];
    ct[i] = sum;
    sum += t;
  }
  for (int i = 0; i < n; ++i) nw[ct[rk[sa[i] + k]]++] = sa[i];
  for (int i = 0; i < n; ++i) sa[i] = nw[i];
}
void calc(int _n, char *_s) {
  n = _n, s = _s;
  std::fill(rk, rk + MAXN, 0);
  for (int i = 0; i < n; ++i) {
    sa[i] = i;
    rk[i] = s[i] - ALPHA_OFFSET;
  }
  for (int k = 1; k < n; k <<= 1) {
    bucket_sort(k);
    bucket_sort(0);
    nw[sa[0]] = 0;
    for (int i = 1; i < n; ++i)
      nw[sa[i]] = nw[sa[i - 1]] + (rk[sa[i]] != rk[sa[i - 1]] ||
                                   rk[sa[i] + k] != rk[sa[i - 1] + k]);
    for (int i = 0; i < n; ++i) rk[i] = nw[i];
  }
  int h = 0;
  lcp[0] = 0, lcp[n] = -1;
  for (int i = 0; i < n; ++i) {
    int j = sa[rk[i] - 1];
    for (h > 0 && --h; i + h < n && j + h < n && s[i + h] == s[j + h]; ++h)
      ;
    lcp[rk[i] - 1] = h;
  }
  for (int i = 0; i < n; ++i) st[i][0] = lcp[i];
  for (int j = 1; j < LOGN; ++j)
    for (int i = 0; i <= n - (1 << j); ++i)
      st[i][j] = std::min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
inline int get_lcp(int p, int q) {
  if (p > q) std::swap(p, q);
  --q;
  int sz = 8 * sizeof(int) - __builtin_clz(q - p) - 1;
  return std::min(st[p][sz], st[q - (1 << sz) + 1][sz]);
}
}  // namespace sfx
char s[MAXN], t[MAXN];
int slen, tlen, n;
int q, l[MAXQ], r[MAXQ], k[MAXQ], x[MAXQ], y[MAXQ], ans[MAXQ];
inline int cmp_substring(const int p, const int q, const int len) {
  if (sfx::get_lcp(sfx::rk[p], sfx::rk[q]) >= len)
    return 0;
  else
    return sfx::rk[p] < sfx::rk[q] ? -1 : +1;
}
inline bool cmp_options(int p, int q) {
  bool rev = (p > q);
  if (rev) std::swap(p, q);
  static int cur;
  if (q - p >= tlen) {
    if ((cur = cmp_substring(p, slen + 1, tlen)) != 0) return (cur > 0) ^ rev;
    if ((cur = cmp_substring(p + tlen, p, q - p - tlen)) != 0)
      return (cur > 0) ^ rev;
    if ((cur = cmp_substring(slen + 1, q - tlen, tlen)) != 0)
      return (cur > 0) ^ rev;
  } else {
    if ((cur = cmp_substring(slen + 1, p, q - p)) != 0) return (cur < 0) ^ rev;
    if ((cur = cmp_substring(slen + 1 + q - p, slen + 1, tlen - q + p)) != 0)
      return (cur < 0) ^ rev;
    if ((cur = cmp_substring(p, slen + 1 + tlen - q + p, q - p)) != 0)
      return (cur < 0) ^ rev;
  }
  return false;
}
int opt_at[MAXN], opt_rk[MAXN];
template <typename T>
struct rmq {
  std::pair<T, int> f[LOGN][MAXN / 2];
  inline void build(int n, const T *arr) {
    for (int i = 0; i < n; ++i) f[0][i] = std::make_pair(arr[i], i);
    for (int j = 1; j < LOGN; ++j)
      for (int i = 0; i <= n - (1 << j); ++i)
        f[j][i] = std::min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
  }
  inline std::pair<T, int> query(int l, int r) {
    if (l > r)
      return std::make_pair(MAXN, -1);
    else if (l == r)
      return f[0][l];
    int sz = 8 * sizeof(int) - __builtin_clz(r - l) - 1;
    return std::min(f[sz][l], f[sz][r - (1 << sz) + 1]);
  }
};
rmq<int> patrick;
void solve_queries() {
  for (int i = 0; i < q; ++i) ans[i] = -1;
  static int t[MAXN], idx[MAXN], modulo_seg_start[SOLANUM_TUBEROSUM];
  for (int cur_k = SOLANUM_TUBEROSUM - 1; cur_k >= 1; --cur_k) {
    int ttop = 0;
    for (int j = 0; j < cur_k; ++j) {
      modulo_seg_start[j] = ttop;
      for (int k = j; k <= slen; k += cur_k)
        idx[ttop] = k, t[ttop++] = opt_rk[k];
    }
    patrick.build(ttop, t);
    for (int i = 0; i < q; ++i)
      if (k[i] == cur_k) {
        std::pair<int, int> cur = std::make_pair(MAXN, -1);
        for (int rem = x[i]; rem <= y[i]; ++rem) {
          cur = std::min(
              cur, patrick.query(
                       modulo_seg_start[rem] +
                           (int)floor((double)(l[i] - rem - 1) / cur_k) + 1,
                       modulo_seg_start[rem] +
                           (int)floor((double)(r[i] - rem) / cur_k)));
        }
        ans[i] = cur.second == -1 ? -1 : idx[cur.second];
      }
  }
  for (int i = 0; i < q; ++i)
    if (k[i] >= SOLANUM_TUBEROSUM) {
      std::pair<int, int> cur = std::make_pair(MAXN, -1);
      for (int mul = 0; mul <= slen; mul += k[i])
        cur = std::min(cur, patrick.query(std::max(l[i], mul + x[i]),
                                          std::min(r[i], mul + y[i])));
      ans[i] = cur.second == -1 ? -1 : idx[cur.second];
    }
}
int main() {
  for (slen = 0; (s[slen] = getchar()) != ' '; ++slen) slen = slen;
  s[slen] = '\0';
  for (tlen = 0; (t[tlen] = getchar()) != ' '; ++tlen) tlen = tlen;
  t[tlen] = '\0';
  s[slen] = '_';
  for (int i = 0; i < tlen; ++i) s[slen + 1 + i] = t[i];
  s[slen + tlen + 1] = '`';
  s[slen + tlen + 2] = '\0';
  n = slen + tlen + 2;
  sfx::calc(n, s);
  for (int i = 0; i <= slen; ++i) opt_at[i] = i;
  std::stable_sort(opt_at, opt_at + slen + 1, cmp_options);
  for (int i = 0; i <= slen; ++i) opt_rk[opt_at[i]] = i;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i)
    scanf("%d%d%d%d%d", &l[i], &r[i], &k[i], &x[i], &y[i]);
  solve_queries();
  for (int i = 0; i < q; ++i) printf("%d%c", ans[i], i == q - 1 ? '\n' : ' ');
  return 0;
}
