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;
inline int read() {
  int x = 0, c = getchar(), f = 0;
  for (; c > '9' || c < '0'; f = c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + c - '0', c = getchar())
    ;
  return f ? -x : x;
}
inline void write(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + 48);
}
const int N = 200000 + 10, sz = 316, oo = N;
int n, ns, nt, Log2[N], a[N];
struct suffix_array {
  int p, q, k;
  int sa[2][N], rk[2][N], v[N], h[N], d[N][18];
  void getsa(int *sa, int *rk, int *SA, int *RK) {
    for (int i = 1, _y = n; i <= _y; ++i) v[rk[sa[i]]] = i;
    for (int i = n, _y = 1; i >= _y; --i)
      if (sa[i] > k) SA[v[rk[sa[i] - k]]--] = sa[i] - k;
    for (int i = n - k + 1, _y = n; i <= _y; ++i) SA[v[rk[i]]--] = i;
    for (int i = 1, _y = n; i <= _y; ++i)
      RK[SA[i]] = RK[SA[i - 1]] + (rk[SA[i]] != rk[SA[i - 1]] ||
                                   rk[SA[i] + k] != rk[SA[i - 1] + k]);
  }
  void getheight() {
    k = 0;
    int x;
    for (int i = 1, _y = n; i <= _y; ++i)
      if ((x = rk[p][i]) == 1)
        h[x] = 0;
      else {
        int j = sa[p][x - 1];
        for (; a[i + k] == a[j + k]; k++)
          ;
        h[x] = k;
        if (k > 0) k--;
      }
  }
  void initrmq() {
    for (int i = 1, _y = n; i <= _y; ++i) d[i][0] = h[i];
    for (int j = 1, _y = Log2[n]; j <= _y; ++j)
      for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
  }
  void Main() {
    p = 0, q = 1;
    for (int i = 1, _y = n; i <= _y; ++i) v[a[i]]++;
    for (int i = 1, _y = 27; i <= _y; ++i) v[i] += v[i - 1];
    for (int i = 1, _y = n; i <= _y; ++i) sa[p][v[a[i]]--] = i;
    for (int i = 1, _y = n; i <= _y; ++i)
      rk[p][sa[p][i]] = rk[p][sa[p][i - 1]] + (a[sa[p][i]] != a[sa[p][i - 1]]);
    for (k = 1; k < n; k <<= 1, swap(p, q)) getsa(sa[p], rk[p], sa[q], rk[q]);
    getheight();
    initrmq();
  }
  int getlcp(int l, int r) {
    if (l == r) return oo;
    l = rk[p][l], r = rk[p][r];
    if (l > r) swap(l, r);
    l++;
    int k = Log2[r - l + 1];
    return min(d[l][k], d[r - (1 << k) + 1][k]);
  }
  int cmp(int x, int y) {
    int f = 1;
    if (x > y) swap(x, y), f = -1;
    if (x == y) return 0;
    if (y - x >= nt) {
      int lcp = getlcp(ns + 1, x + 1);
      if (lcp < nt) return rk[p][ns + 1] < rk[p][x + 1] ? f : -f;
      lcp = getlcp(x + 1, x + nt + 1);
      if (lcp < y - x - nt) return rk[p][x + 1] < rk[p][x + nt + 1] ? f : -f;
      lcp = getlcp(y - nt + 1, ns + 1);
      if (lcp < nt) return rk[p][y - nt + 1] < rk[p][ns + 1] ? f : -f;
    } else {
      int lcp = getlcp(ns + 1, x + 1);
      if (lcp < y - x) return rk[p][ns + 1] < rk[p][x + 1] ? f : -f;
      lcp = getlcp(ns + y - x + 1, ns + 1);
      if (lcp < nt - y + x)
        return rk[p][ns + y - x + 1] < rk[p][ns + 1] ? f : -f;
      lcp = getlcp(x + 1, ns + nt - y + x + 1);
      if (lcp < y - x)
        return rk[p][x + 1] < rk[p][ns + nt + 1 - y + x] ? f : -f;
    }
    return 0;
  }
} sa;
int id[N], pos[N], d[N][18], ans[N], p[N];
char S[N], T[N];
struct node {
  int l, r, x, y, id;
};
vector<node> small[sz + 10];
bool cmp(const int &x, const int &y) {
  int f = sa.cmp(x, y);
  return f == 1 ? 1 : (f == -1 ? 0 : x < y);
}
void initrmq(int *a, int n) {
  for (int i = 0, _y = n; i <= _y; ++i) d[i][0] = a[i];
  for (int j = 1, _y = Log2[n]; j <= _y; ++j)
    for (int i = 0; i + (1 << j) - 1 <= n; ++i)
      d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
int getans(int l, int r) {
  if (l > r) return oo;
  int k = Log2[r - l];
  return min(d[l][k], d[r - (1 << k) + 1][k]);
}
int work1(int k, int l, int r, int x, int y) {
  int res = oo;
  for (int i = 0; i * k + x <= ns; ++i) {
    int L = i * k + x, R = i * k + y;
    if (R < l || r < L) continue;
    L = max(l, L);
    R = min(r, R);
    res = min(res, getans(L, R));
  }
  return res;
}
void work2(int k, vector<node> &Vec) {
  for (int i = 0, _y = k - 1; i <= _y; ++i) {
    int tot = -1;
    for (int j = i; j <= ns; j += k) p[++tot] = pos[j];
    initrmq(p, tot);
    for (int j = 0, _y = Vec.size() - 1; j <= _y; ++j) {
      node t = Vec[j];
      if (t.x > i || i > t.y) continue;
      int L = (t.l - i) / k, R = (t.r - i) / k;
      L += L * k + i < t.l;
      R += R * k + k + i <= t.r;
      if (R * k + i > t.r) continue;
      L = max(L, 0);
      R = min(R, tot);
      ans[t.id] = min(ans[t.id], getans(L, R));
    }
  }
}
int q;
int main() {
  scanf("%s%s%d", S + 1, T + 1, &q);
  ns = strlen(S + 1);
  nt = strlen(T + 1);
  for (int i = 1, _y = ns; i <= _y; ++i) a[++n] = S[i] - 'a' + 1;
  for (int i = 1, _y = nt; i <= _y; ++i) a[++n] = T[i] - 'a' + 1;
  for (int i = 2, _y = n; i <= _y; ++i) Log2[i] = Log2[i >> 1] + 1;
  sa.Main();
  for (int i = 0, _y = ns; i <= _y; ++i) id[i] = i;
  sort(id, id + ns + 1, cmp);
  for (int i = 0, _y = ns; i <= _y; ++i) pos[id[i]] = i;
  initrmq(pos, ns);
  for (int i = 1, _y = q; i <= _y; ++i) {
    int l = read(), r = read(), k = read(), x = read(), y = read();
    if (k >= sz)
      ans[i] = work1(k, l, r, x, y);
    else
      ans[i] = oo, small[k].push_back((node){l, r, x, y, i});
  }
  for (int i = 1, _y = sz - 1; i <= _y; ++i)
    if (small[i].size()) work2(i, small[i]);
  for (int i = 1, _y = q; i <= _y; ++i)
    write(ans[i] == oo ? -1 : id[ans[i]]), putchar(i == q ? '\n' : ' ');
}
