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 suffix_array {
  const int INF = 0x7fffffff;
  int L, D;
  string str;
  vector<vector<int> > suff;
  vector<int> rank_of, at_rank;
  pair<pair<int, int>, int> __make_rep(int l, int i, int p) {
    if (!l) return {{str[i], INF}, i};
    return {{suff[l - 1][i], (i + p < L) ? suff[l - 1][i + p] : INF}, i};
  }
  suffix_array(string _str) {
    str = _str;
    L = str.size();
    D = 33 - __builtin_clz(L - 1);
    suff.resize(D);
    vector<pair<pair<int, int>, int> > keys(L);
    for (int l = 0; l < D; l++) {
      for (int i = 0; i < L; i++) keys[i] = __make_rep(l, i, 1 << (l - 1));
      sort(keys.begin(), keys.end());
      suff[l].resize(L);
      for (int i = 0, r = 0; i < L; i++) {
        if (i > 0 && keys[i].first != keys[i - 1].first) r++;
        suff[l][keys[i].second] = r;
      }
    }
    rank_of.resize(L);
    at_rank.resize(L);
    for (int i = 0; i < L; i++) {
      rank_of[i] = suff.back()[i];
      at_rank[rank_of[i]] = i;
    }
  }
  int comp(int i, int l1, int j, int l2) {
    int cl = min(l1, l2);
    for (int l = 0; l < D; l++)
      if ((cl >> l) & 1) {
        if (suff[l][i] != suff[l][j]) return suff[l][i] < suff[l][j] ? -1 : 1;
        i += 1 << l, j += 1 << l;
      }
    return (l1 != l2) ? (l1 < l2) ? -1 : 1 : 0;
  }
};
int adj(int ins, int inx, int len, int N, int M) {
  if (inx < ins) return inx;
  if (inx >= ins + M) return inx - M;
  return N + inx - ins;
}
struct RMQ {
  vector<vector<int> > mv;
  RMQ(vector<int> &_vals) {
    int N = _vals.size();
    mv.push_back(_vals);
    int pw2 = 1;
    for (int l = 1; pw2 <= N; l++) {
      pw2 *= 2;
      vector<int> nxt = mv.back();
      for (int i = 0; i < N; i++) {
        int inx = i + (1 << (l - 1));
        if (inx < N) nxt[i] = min(nxt[i], mv.back()[inx]);
      }
      mv.push_back(nxt);
    }
  }
  int read(int i, int j) {
    if (i > j) return INT_MAX;
    int len = j - i + 1;
    int pw2 = 1, lvl = 0;
    while (pw2 * 2 <= len) {
      pw2 *= 2;
      lvl++;
    }
    return min(mv[lvl][i], mv[lvl][j - pw2 + 1]);
  }
};
const int LIM = 200;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  string S, T;
  cin >> S >> T;
  int N = S.size(), M = T.size();
  stringstream st;
  st << S << T;
  suffix_array sa(st.str());
  vector<int> opts(N + 1);
  for (int i = 0; i <= N; i++) opts[i] = i;
  stable_sort((opts).begin(), (opts).end(), [&](int i, int j) {
    vector<int> pts = {0, i, j, i + M, j + M, M + N};
    sort((pts).begin(), (pts).end());
    pts.erase(unique((pts).begin(), (pts).end()), pts.end());
    for (int k = 0; k + 1 < pts.size(); k++) {
      int inx = pts[k], len = pts[k + 1] - pts[k];
      int res =
          sa.comp(adj(i, inx, len, N, M), len, adj(j, inx, len, N, M), len);
      if (res != 0) return res == -1;
    }
    return false;
  });
  vector<int> rank(N + 1);
  for (int i = 0; i <= N; i++) {
    rank[opts[i]] = i;
  };
  ;
  RMQ whole(rank);
  int Q;
  cin >> Q;
  vector<int> l(Q), r(Q), k(Q), x(Q), y(Q), ans(Q, INT_MAX);
  vector<vector<int> > which(LIM);
  for (int q = 0; q < Q; q++) {
    cin >> l[q] >> r[q] >> k[q] >> x[q] >> y[q];
    x[q] = min(x[q], k[q] - 1);
    y[q] = min(y[q], k[q] - 1);
    if (k[q] >= LIM) {
      for (int g = 0; g <= N; g += k[q]) {
        int gx = g + x[q], gy = g + y[q];
        gx = max(gx, l[q]);
        gy = min(gy, r[q]);
        if (gx <= gy) ans[q] = min(ans[q], whole.read(gx, gy));
      }
    } else {
      which[k[q]].push_back(q);
    }
  }
  for (int siz = 1; siz < LIM; siz++) {
    vector<RMQ> small;
    for (int rem = 0; rem < siz; rem++) {
      vector<int> elts;
      for (int i = rem; i <= N; i += siz) elts.push_back(rank[i]);
      small.push_back(RMQ(elts));
    }
    for (int q : which[siz]) {
      for (int rem = x[q]; rem <= y[q]; rem++) {
        int a = (l[q] % k[q] <= rem) ? l[q] / k[q] : (l[q] / k[q] + 1);
        int b = (r[q] % k[q] >= rem) ? r[q] / k[q] : (r[q] / k[q] - 1);
        ans[q] = min(ans[q], small[rem].read(a, b));
      }
    }
  }
  for (int i = 0; i < Q; i++) {
    cout << (ans[i] == INT_MAX ? -1 : opts[ans[i]]) << " ";
  }
  cout << endl;
  return 0;
}
