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;
ostream& operator<<(ostream& ss, pair<int, int> p) {
  return (ss << "(" << p.first << "," << p.second << ")");
}
namespace SA {
const int MAXN = 220000;
const int MAXLG = 20;
int n, t;
int ra[MAXN], sa[MAXN], h[MAXN];
string s;
int rmq[MAXLG][MAXN];
int log2[MAXN];
void suff_arr() {
  n = s.size();
  int N = n + 256;
  for (int i = 0; i < n; i++) sa[i] = i, ra[i] = s[i];
  for (int k = 0; k < n; k ? k *= 2 : k++) {
    vector<int> nsa(sa, sa + n), nra(n), cnt(N);
    for (int i = 0; i < n; i++) nsa[i] = (nsa[i] - k + n) % n;
    for (int i = 0; i < n; i++) cnt[ra[i]]++;
    for (int i = 1; i < N; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--cnt[ra[nsa[i]]]] = nsa[i];
    int r = 0;
    for (int i = 1; i < n; i++) {
      if (ra[sa[i]] != ra[sa[i - 1]])
        r++;
      else if (ra[(sa[i] + k) % n] != ra[(sa[i - 1] + k) % n])
        r++;
      nra[sa[i]] = r;
    }
    for (int(i) = (0); (i) < (n); (i)++) ra[i] = nra[i];
  }
}
void initlcp() {
  int tam = 0, j;
  for (int(i) = (0); (i) < (n - 1); (i)++) {
    j = sa[ra[i] - 1];
    while (s[i + tam] == s[j + tam]) ++tam;
    h[ra[i] - 1] = tam;
    if (tam > 0) --tam;
  }
}
void makelcp() {
  initlcp();
  for (int(i) = (0); (i) < (n - 1); (i)++) rmq[0][i] = h[i];
  int lg = 0, pw = 1;
  do {
    for (int(i) = (pw); (i) < (pw * 2); (i)++) log2[i] = lg;
    lg++;
    pw *= 2;
    for (int(i) = (0); (i) < (n - 1); (i)++) {
      if (i + pw / 2 < n - 1)
        rmq[lg][i] = min(rmq[lg - 1][i], rmq[lg - 1][i + pw / 2]);
      else
        rmq[lg][i] = rmq[lg - 1][i];
    }
  } while (pw < n);
}
int lcp(int i, int j) {
  if (i > j) swap(i, j);
  if (i == j) return n - sa[i] - 1;
  j--;
  int lg = log2[j - i + 1], pw = (1 << lg);
  return min(rmq[lg][i], rmq[lg][j - pw + 1]);
}
int comp(int i, int j, int len) {
  if (len <= 0) return 0;
  int u = ra[i];
  int v = ra[j];
  if (lcp(u, v) >= len)
    return 0;
  else if (ra[i] < ra[j])
    return 1;
  else
    return -1;
}
};  // namespace SA
const int INF = 1e9;
int n, m, q;
string s, t;
int comp(int i, int j) {
  if (i == j) return 0;
  if (i > j) return -comp(j, i);
  int len = min(m, j - i);
  int cmp = SA::comp(n + 1, i, len);
  if (cmp) return cmp;
  if (j - i < m) {
    cmp = SA::comp(n + 1 + (j - i), n + 1, m - (j - i));
    if (cmp) return cmp;
    cmp = SA::comp(i, n + 1 + m - (j - i), j - i);
    if (cmp) return cmp;
    return 0;
  } else {
    cmp = SA::comp(i, i + m, (j - i) - m);
    if (cmp) return cmp;
    cmp = SA::comp(i + (j - i) - m, n + 1, m);
    if (cmp) return cmp;
    return 0;
  }
}
int scmp(int i, int j) {
  if (comp(i, j) == 1) return 1;
  if (comp(i, j) == -1) return 0;
  return i < j;
}
int rnk[220000];
int ord[220000];
struct segment {
  int n;
  vector<pair<int, int> > t;
  segment() {}
  segment(int n) : n(n) { t = vector<pair<int, int> >(2 * n); }
  void build() {
    for (int i = n - 1; i > 0; i--) t[i] = min(t[i << 1], t[i << 1 | 1]);
  }
  pair<int, int> query(int l, int r) {
    pair<int, int> ans = make_pair((INF), (INF));
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = min(ans, t[l++]);
      if (r & 1) ans = min(t[--r], ans);
    }
    return ans;
  }
} SEG;
struct query {
  int l, r;
  int x, y;
  int id;
  query(int l, int r, int x, int y, int id) : l(l), r(r), x(x), y(y), id(id) {}
};
vector<query> vec[500];
pair<int, int> ans[110000];
int rt;
vector<pair<int, int> > a[500];
segment st[500];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ;
  cin >> s >> t >> q;
  n = ((int)s.size());
  m = ((int)t.size());
  SA::s.resize(n + m + 2);
  for (int(i) = (0); (i) < (n); (i)++) SA::s[i] = s[i];
  SA::s[n] = '$';
  for (int(i) = (0); (i) < (m); (i)++) SA::s[n + 1 + i] = t[i];
  SA::s[n + m + 1] = '$';
  SA::suff_arr();
  SA::makelcp();
  for (int(i) = (0); (i) < (n + 1); (i)++) ord[i] = i;
  sort(ord, ord + n + 1, scmp);
  n++;
  for (int(i) = (0); (i) < (n); (i)++) rnk[ord[i]] = i;
  SEG = segment(n);
  for (int(i) = (0); (i) < (n); (i)++) SEG.t[n + i] = make_pair((rnk[i]), (i));
  SEG.build();
  rt = sqrt(n);
  for (int(k) = (0); (k) < (rt); (k)++) vec[k].clear();
  for (int(i) = (0); (i) < (q); (i)++) {
    int l, r, k, x, y;
    cin >> l >> r >> k >> x >> y;
    ans[i] = make_pair((INF), (INF));
    if (k >= rt) {
      while (x < n) {
        ans[i] = min(ans[i], SEG.query(max(l, x), min(r + 1, min(y + 1, n))));
        x += k;
        y += k;
      }
    } else
      vec[k].push_back(query(l, r, x, y, i));
  }
  for (int(k) = (1); (k) < (rt); (k)++) {
    if (vec[k].empty()) continue;
    for (int(i) = (0); (i) < (k); (i)++) a[i].clear();
    for (int(i) = (0); (i) < (n); (i)++)
      a[i % k].push_back(make_pair((rnk[i]), (i)));
    for (int(i) = (0); (i) < (k); (i)++) {
      st[i] = segment(((int)a[i].size()));
      for (int(j) = (0); (j) < (((int)a[i].size())); (j)++)
        st[i].t[((int)a[i].size()) + j] = a[i][j];
      st[i].build();
    }
    for (query z : vec[k]) {
      for (int(i) = (z.x); (i) < (z.y + 1); (i)++) {
        if (i > z.r) continue;
        int lo = (z.l - i + (k - 1)) / k;
        int hi = (z.r - i) / k;
        ans[z.id] =
            min(ans[z.id], st[i].query(max(lo, 0), min(hi + 1, st[i].n)));
      }
    }
  }
  for (int(i) = (0); (i) < (q); (i)++) {
    if (ans[i].second == INF)
      cout << -1 << " ";
    else
      cout << ans[i].second << " ";
  }
  cout << endl;
  return 0;
}
