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;
const int N = 400005;
int ls, lt, id[N], n, rnk[N], L, R, lim = 0;
char S[N];
vector<int> V[10000];
struct ques {
  int x, y, l, r, k, ans;
} q[N];
struct suffix_array {
  int sa[N], rk[N], hr[N], hs[N];
  int tmp[N], bin[N], sz;
  void build(char *S, int ls) {
    sz = max(255, ls);
    for (int i = (1); i <= (ls); ++i) rk[i] = S[i];
    for (int i = (1); i <= (sz); ++i) bin[i] = 0;
    for (int i = (1); i <= (ls); ++i) bin[rk[i]]++;
    for (int i = (1); i <= (sz); ++i) bin[i] += bin[i - 1];
    for (int i = (1); i <= (ls); ++i) sa[bin[rk[i]]--] = i;
    for (int j = 1; j <= ls; j <<= 1) {
      int tot = 0;
      for (int i = (ls - j + 1); i <= (ls); ++i) tmp[++tot] = i;
      for (int i = (1); i <= (ls); ++i)
        if (sa[i] - j > 0) tmp[++tot] = sa[i] - j;
      for (int i = (1); i <= (sz); ++i) bin[i] = 0;
      for (int i = (1); i <= (ls); ++i) bin[rk[i]]++;
      for (int i = (1); i <= (sz); ++i) bin[i] += bin[i - 1];
      for (int i = (ls); i >= (1); --i) sa[bin[rk[tmp[i]]]--] = tmp[i];
      tot = 1;
      tmp[sa[1]] = 1;
      for (int i = (2); i <= (ls); ++i)
        tmp[sa[i]] =
            rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + j] == rk[sa[i - 1] + j]
                ? tot
                : ++tot;
      for (int i = (1); i <= (ls); ++i) rk[i] = tmp[i];
      if (ls == tot) break;
    }
    for (int i = (1); i <= (ls); ++i) {
      hs[i] = max(hs[i - 1] - 1, 0);
      while (S[i + hs[i]] == S[sa[rk[i] - 1] + hs[i]]) hs[i]++;
      hr[rk[i]] = hs[i];
    }
  }
} SA;
struct st_table {
  int mn[30][400005], lg2[400005];
  void init(int *h, int n) {
    for (int i = (1); i <= (n); ++i) mn[0][i] = h[i];
    for (int k = (1); k <= (25); ++k)
      for (int i = (1); i <= (n + 1 - (1 << k)); ++i)
        mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
    lg2[1] = 0;
    for (int i = (2); i <= (n); ++i) lg2[i] = lg2[i >> 1] + 1;
  }
  int lcp(int x, int y) {
    if (x == y) return 1 << 26;
    x = SA.rk[x];
    y = SA.rk[y];
    if (x > y) swap(x, y);
    x++;
    int t = lg2[y - x + 1];
    return min(mn[t][x], mn[t][y - (1 << t) + 1]);
  }
} ST;
struct st_table_rnk {
  int mn[30][400005], a[N], lg2[400005];
  int smin(int x, int y) {
    if (a[x] < a[y])
      return x;
    else
      return y;
  }
  void init(int *h, int n) {
    for (int i = (1); i <= (n); ++i) a[i] = h[i], mn[0][i] = i;
    for (int k = (1); k <= (25); ++k)
      for (int i = (1); i <= (n + 1 - (1 << k)); ++i)
        mn[k][i] = smin(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
    lg2[1] = 0;
    for (int i = (2); i <= (n); ++i) lg2[i] = lg2[i >> 1] + 1;
  }
  int get(int x, int y) {
    if (x > y) return 0;
    int t = lg2[y - x + 1];
    return smin(mn[t][x], mn[t][y - (1 << t) + 1]);
  }
} STR;
bool cmps(int a, int b) {
  int bj = 0, L, x;
  if (a > b) swap(a, b), bj = 1;
  if (a + lt > b) {
    x = lt - (b - a);
    L = ST.lcp(ls + 2, a);
    if (L < b - a) return bj ^ (S[ls + 2 + L] < S[a + L]);
    L = ST.lcp(ls + 2 + b - a, ls + 2);
    if (L < x) return bj ^ (S[ls + 2 + b - a + L] < S[ls + 2 + L]);
    L = ST.lcp(a, ls + 2 + x);
    if (L < b - a) return bj ^ (S[a + L] < S[ls + 2 + x + L]);
  } else if (a + lt == b) {
    L = ST.lcp(ls + 2, a);
    if (L < lt) return bj ^ (S[ls + 2 + L] < S[a + L]);
    L = ST.lcp(a, ls + 2);
    if (L < lt) return bj ^ (S[a + L] < S[ls + 2 + L]);
  } else if (a + lt < b) {
    x = (b - a) - lt;
    L = ST.lcp(ls + 2, a);
    if (L < lt) return bj ^ (S[ls + 2 + L] < S[a + L]);
    L = ST.lcp(a, a + lt);
    if (L < x) return bj ^ (S[a + L] < S[a + lt + L]);
    L = ST.lcp(a + x, ls + 2);
    if (L < lt) return bj ^ (S[a + x + L] < S[ls + 2 + L]);
  }
  return bj ^ 1;
}
struct st_table_r {
  vector<int> mn[30], lg2;
  int smin(int x, int y) {
    if (rnk[x] < rnk[y])
      return x;
    else
      return y;
  }
  void clear(int n) {
    for (int i = (0); i <= (29); ++i) mn[i].resize(n + 2);
    lg2.resize(n + 2);
    for (int j = (0); j <= (n + 1); ++j) {
      for (int i = (0); i <= (28); ++i) mn[i][j] = 0;
      lg2[j] = 0;
    }
  }
  void init(int n) {
    for (int k = (1); k <= (25); ++k)
      for (int i = (1); i <= (n + 1 - (1 << k)); ++i)
        mn[k][i] = smin(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
    lg2[1] = 0;
    for (int i = (2); i <= (n); ++i) lg2[i] = lg2[i >> 1] + 1;
  }
  int get(int x, int y) {
    if (x > y) return 0;
    int t = lg2[y - x + 1];
    return smin(mn[t][x], mn[t][y - (1 << t) + 1]);
  }
} STr[10000];
void work(int K) {
  if (V[K].size() == 0) return;
  for (int i = (0); i <= (K - 1); ++i) STr[i].clear(ls / K + 1);
  for (int i = (1); i <= (ls + 1); ++i)
    STr[(i - 1) % K].mn[0][(i - 1) / K + 1] = i;
  for (int i = (0); i <= (K - 1); ++i) STr[i].init(ls / K + 1);
  for (int i = (0); i <= (V[K].size() - 1); ++i) {
    int w = V[K][i];
    q[w].ans = -1;
    for (int j = (q[w].x); j <= (q[w].y); ++j) {
      L = (q[w].l - j) / K;
      if (L * K + j < q[w].l) L++;
      R = (q[w].r - j) / K;
      if (R * K + j > q[w].r) R--;
      int z = STr[j].get(L + 1, R + 1);
      if (rnk[q[w].ans + 1] > rnk[z]) q[w].ans = z - 1;
    }
  }
}
int main() {
  scanf("%s", S + 1);
  ls = strlen(S + 1);
  S[ls + 1] = 13;
  scanf("%s", S + ls + 2);
  lt = strlen(S + 1) - ls - 1;
  SA.build(S, ls + lt + 1);
  for (int i = (1); i <= (ls + 1); ++i) id[i] = i;
  ST.init(SA.hr, ls + lt + 1);
  sort(id, id + ls + 2, cmps);
  for (int i = (1); i <= (ls + 1); ++i) rnk[id[i]] = i;
  scanf("%d", &n);
  lim = sqrt(1.0 * n / log2(n));
  STR.init(rnk, ls + 1);
  rnk[0] = 1 << 29;
  for (int i = (1); i <= (n); ++i) {
    scanf("%d%d%d%d%d", &q[i].l, &q[i].r, &q[i].k, &q[i].x, &q[i].y);
    if (q[i].k > lim) {
      q[i].ans = -1;
      for (int j = (0); j <= (ls / q[i].k); ++j) {
        L = max(q[i].l, q[i].x + j * q[i].k);
        R = min(q[i].r, q[i].y + j * q[i].k);
        int z = STR.get(L + 1, R + 1);
        if (rnk[q[i].ans + 1] > rnk[z]) q[i].ans = z - 1;
      }
    } else
      V[q[i].k].push_back(i);
  }
  for (int i = (1); i <= (lim); ++i) work(i);
  for (int i = (1); i <= (n); ++i) printf("%d ", q[i].ans);
}
