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;
int in() {
  int32_t x;
  scanf("%d", &x);
  return x;
}
inline long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
const int maxn = 2e5 + 10;
const int SQ = 448 + 10;
struct query {
  int l, r, k, x, y, id;
  inline void read() { l = in(), r = in(), k = in(), x = in(), y = in(); }
  inline bool operator<(const query &b) const { return k < b.k; }
} Q[maxn];
bool fl;
int suffix[20][maxn];
string s, t, cont;
pair<pair<int, int>, int> ptr[maxn];
pair<int, int> segmentsA[4], segmentsB[4];
int id[maxn];
int N, M;
inline int get_rank(int cur, int ln, int a) {
  if (cur + (1 << ln) <= a) {
    return suffix[ln][cur];
  }
  if (cur >= a && cur + (1 << ln) <= a + M) {
    return suffix[ln][cur - a + N];
  }
  if (cur >= a + M) return suffix[ln][cur - M];
  return -2;
}
inline bool cmp(int a, int b) {
  int cur = 0;
  int lim = N + M;
  for (int pt = 0; pt < 5; pt++) {
    for (int ln = 19; ln >= 0; ln--) {
      if (cur + (1 << ln) > lim + 1) continue;
      int Acmp = get_rank(cur, ln, a), Bcmp = get_rank(cur, ln, b);
      if (Acmp == -2 || Bcmp == -2) continue;
      cur += (1 << ln);
      if (Acmp != Bcmp) return Acmp < Bcmp;
    }
  }
  return a < b;
}
int optionRank[maxn];
pair<int, int> mini[20][maxn], mini_[20][maxn];
inline void build() {
  cont = s + t;
  N = (int)s.size();
  M = (int)t.size();
  int n = (int)cont.size();
  for (int i = 0; i < n; i++) ptr[i] = {{cont[i], cont[i]}, i};
  sort(ptr, ptr + n);
  for (int i = 0; i < n; i++)
    suffix[0][ptr[i].second] =
        (i && ptr[i].first == ptr[i - 1].first ? suffix[0][ptr[i - 1].second]
                                               : i);
  for (int i = 1; i < 20; i++) {
    for (int j = 0; j < n; j++)
      ptr[j] = {
          {suffix[i - 1][j],
           (1 << (i - 1)) + j < n ? suffix[i - 1][j + (1 << (i - 1))] : -1},
          j};
    sort(ptr, ptr + n);
    for (int j = 0; j < n; j++)
      suffix[i][ptr[j].second] =
          (j && ptr[j].first == ptr[j - 1].first ? suffix[i][ptr[j - 1].second]
                                                 : j);
  }
  for (int i = 0; i <= n; i++) id[i] = i;
  sort(id, id + N + 1, cmp);
  for (int i = 0; i <= N; i++)
    optionRank[id[i]] =
        (i && cmp(id[i], id[i - 1]) == 1 ? optionRank[id[i - 1]] : i);
  memset(mini_, 63, sizeof mini_);
  for (int i = 0; i <= N; i++) mini_[0][i] = {optionRank[i], i};
  for (int j = 1; j < 20; j++)
    for (int i = 0; i + (1 << j) <= N; i++)
      mini_[j][i] = min(mini_[j - 1][i], mini_[j - 1][i + (1 << (j - 1))]);
}
vector<int> vc[maxn];
int lg2[maxn];
int zarib;
int rem;
int __offset[maxn];
inline void build_rmq(vector<int> &a, int offset = 0) {
  int n = a.size();
  for (int i = 0; i < a.size(); i++)
    mini[0][i + offset] = {a[i], i * zarib + rem};
  for (int j = 1; j < 20; j++)
    for (int i = 0; i + (1 << j) <= n; i++)
      mini[j][i + offset] = min(mini[j - 1][i + offset],
                                mini[j - 1][i + (1 << (j - 1)) + offset]);
}
inline void build_(int mod) {
  for (int i = 0; i <= mod; i++) vc[i].clear();
  for (int i = 0; i <= N; i++) vc[i % mod].push_back(optionRank[i]);
  int sum = 0;
  zarib = mod;
  for (int i = 0; i < mod; i++) {
    rem = i;
    build_rmq(vc[i], sum);
    __offset[i] = sum;
    sum += vc[i].size();
  }
}
inline pair<int, int> get_mini(int id, int a, int b) {
  if (a > b) return {maxn, maxn};
  int len = b - a + 1;
  int lg = lg2[len];
  return min(mini[lg][__offset[id] + a],
             mini[lg][b - (1 << lg) + 1 + __offset[id]]);
}
inline pair<int, int> get_mini_(int a, int b) {
  if (a > b) return {maxn, maxn};
  int len = b - a + 1;
  int lg = lg2[len];
  return min(mini_[lg][a], mini_[lg][b - (1 << lg) + 1]);
}
pair<int, int> ans[maxn];
int32_t main() {
  cin >> s >> t;
  build();
  int q = in();
  for (int i = 2; i < maxn; i++) lg2[i] = lg2[i / 2] + 1;
  for (int i = 0; i < q; i++) Q[i].read(), Q[i].id = i;
  sort(Q, Q + q);
  for (int i = 0; i < q; i++) ans[i].first = ans[i].second = maxn;
  for (int i = 0; i < q; i++) {
    if (Q[i].k < SQ) {
      if (i == 0 || Q[i - 1].k != Q[i].k) build_(Q[i].k);
      for (int pt = Q[i].x; pt <= Q[i].y; pt++) {
        int first = Q[i].l + ((pt - (Q[i].l % Q[i].k) + Q[i].k) % Q[i].k);
        int finish = Q[i].r - (((Q[i].r % Q[i].k) - pt + Q[i].k) % Q[i].k);
        if (first <= finish) {
          pair<int, int> best = get_mini(pt, first / Q[i].k, finish / Q[i].k);
          ans[Q[i].id] = min(ans[Q[i].id], best);
        }
      }
    } else {
      for (int pt = 0; pt <= N; pt += Q[i].k) {
        int L, R;
        L = pt + Q[i].x;
        R = pt + Q[i].y;
        L = max(L, Q[i].l);
        R = min(R, Q[i].r);
        pair<int, int> best = get_mini_(L, R);
        ans[Q[i].id] = min(ans[Q[i].id], best);
      }
    }
  }
  for (int i = 0; i < q; i++)
    printf("%d ", (ans[i].first == maxn ? -1 : ans[i].second));
}
