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;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "yes" : "no");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long double lg[200135];
struct SuffixArray {
  int sa[200135], rk[200135], height[200135];
  int c[200135], x[200135], y[200135];
  void get_SA1(const char *s, int n, int m = 122) {
    for (int(i) = 1; (i) <= (int)(n); (i)++) ++c[x[i] = s[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
      int num = 0;
      for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
      for (int i = 1; i <= n; ++i)
        if (sa[i] > k) y[++num] = sa[i] - k;
      for (int i = 1; i <= m; ++i) c[i] = 0;
      for (int i = 1; i <= n; ++i) ++c[x[i]];
      for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
      for (int i = n; i >= 1; --i) {
        sa[c[x[y[i]]]--] = y[i];
        y[i] = 0;
      }
      swap(x, y);
      x[sa[1]] = 1;
      num = 1;
      for (int i = 2; i <= n; ++i)
        x[sa[i]] =
            (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                ? num
                : ++num;
      if (num == n) break;
      m = num;
    }
  }
  void get_height(const char *s, int n) {
    int k = 0;
    for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
    for (int i = 1; i <= n; ++i) {
      if (rk[i] == 1) continue;
      if (k) --k;
      int j = sa[rk[i] - 1];
      while (j + k <= n && i + k <= n && s[i + k] == s[j + k]) ++k;
      height[rk[i]] = k;
    }
  }
  void ppTest(const char *s, int n) {
    for (int(i) = 1; (i) <= (int)(n); (i)++) {
      printf("%d: %d ", i, sa[i]);
      for (int j = sa[i]; j <= n; j++) printf("%c", s[j]);
      puts("");
    }
  }
} sa;
struct SuffixStQuery {
  int T[200135][20];
  void init(int n) {
    for (int(i) = 1; (i) <= (int)(n); (i)++) T[i][0] = sa.height[i];
    for (int j = 1; (1 << j) <= n; j++) {
      for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        T[i][j] = min(T[i][j - 1], T[i + (1 << (j - 1))][j - 1]);
      }
    }
    for (int(i) = 1; (i) <= (int)(n); (i)++) lg[i] = log(i);
  }
  int qym(int l, int r) {
    if (r < l) swap(l, r);
    int x = lg[r - l + 1] / lg[2];
    int y = min(T[l][x], T[r - (1 << x) + 1][x]);
    return y;
  }
} stQuery;
char S[200135];
int Q, ls, lt;
int cmpStr(int i, int j, int len) {
  if (i == j) return 0;
  int lcp = stQuery.qym(min(sa.rk[i], sa.rk[j]) + 1, max(sa.rk[i], sa.rk[j]));
  if (len <= lcp) return 0;
  assert(i + lcp <= ls + lt && j + lcp <= ls + lt);
  assert(S[i + lcp] != S[j + lcp]);
  return S[i + lcp] < S[j + lcp] ? 1 : -1;
}
int cmp(int p1, int p2) {
  if (p1 == p2) return 0;
  if (p1 > p2) return -cmp(p2, p1);
  if (p1 + lt >= p2 + 1) {
    int z = cmpStr(ls + 1, p1 + 1, p2 - p1);
    if (z != 0) return z;
    int cc = p2 - p1;
    z = cmpStr(ls + 1 + cc, ls + 1, lt - cc);
    if (z != 0) return z;
    cc = lt - cc;
    return cmpStr(p1 + 1, ls + 1 + cc, lt - cc);
  } else {
    int z = cmpStr(ls + 1, p1 + 1, lt);
    if (z != 0) return z;
    z = cmpStr(p1 + 1, p1 + 1 + lt, p2 + 1 - (p1 + 1 + lt));
    if (z != 0) return z;
    int cc = p2 + 1 - (p1 + 1 + lt);
    return cmpStr(p1 + 1 + cc, ls + 1, lt);
  }
}
bool smp(int a, int b) {
  int z = cmp(a, b);
  if (z == 0) return a < b;
  return z == 1;
}
int ynk[200135], rid[200135];
void init() {
  sa.get_SA1(S, ls + lt);
  sa.get_height(S, ls + lt);
  stQuery.init(ls + lt);
  n = ls;
  for (int(i) = 1; (i) <= (int)(n); (i)++) ynk[i] = i;
  sort(ynk, ynk + n + 1, smp);
  for (int i = 0; i <= n; i++) rid[ynk[i]] = i;
}
struct mb {
  int l, r, x, y, k, id;
  void rd(int i) {
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    id = i;
  }
} q[200135];
vector<int> ks[200135];
int sq, L[200135], R[200135], Ans[200135];
int sT[200135][20];
int qym(int l, int r) {
  if (r < l) swap(l, r);
  int x = lg[r - l + 1] / lg[2];
  int y = min(sT[l][x], sT[r - (1 << x) + 1][x]);
  return y;
}
int gid(int K, int k, int x) {
  int z = x / K;
  if ((x % K) >= k) z++;
  return z;
}
void deal(int K) {
  int cnt = 0;
  for (int i = 0; i < K; i++) {
    L[i] = -1;
    R[i] = -1;
    for (int j = i; j <= n; j += K) {
      ++cnt;
      sT[cnt][0] = rid[j];
      if (j == i) L[i] = cnt;
    }
    R[i] = cnt;
  }
  for (int j = 1; (1 << j) <= cnt; j++) {
    for (int i = 1; i + (1 << j) - 1 <= cnt; i++) {
      sT[i][j] = min(sT[i][j - 1], sT[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int qid : ks[K]) {
    for (int j = q[qid].x; j <= q[qid].y; j++) {
      if (L[j] == -1) continue;
      int x = gid(K, j, q[qid].l), y = gid(K, j, q[qid].r);
      int X = L[j] + x - 1;
      int Y = L[j] + y - 1;
      if (q[qid].l % K != j) X++;
      if (Y < X) continue;
      Ans[qid] = min(Ans[qid], qym(X, Y));
    }
  }
}
void fmain() {
  scanf("%s", S + 1);
  ls = strlen(S + 1);
  scanf("%s", S + ls + 1);
  lt = strlen(S + 1 + ls);
  scanf("%d", &Q);
  init();
  for (int(i) = 1; (i) <= (int)(Q); (i)++) {
    q[i].rd(i);
    ks[q[i].k].push_back(i);
    Ans[i] = (1 << 30);
  }
  sq = 77;
  for (int(i) = 1; (i) <= (int)(sq); (i)++) deal(i);
  for (int i = 0; i <= n; i++) sT[i + 1][0] = rid[i];
  for (int j = 1; (1 << j) <= n + 1; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n + 1; i++) {
      sT[i][j] = min(sT[i][j - 1], sT[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int K = sq + 1; K <= n; K++)
    if (!ks[K].empty()) {
      for (int qid : ks[K]) {
        for (int i = q[qid].x, j = q[qid].y; i <= n; i += K, j += K) {
          int x = max(i, q[qid].l), y = min(j, q[qid].r);
          if (y < x) continue;
          Ans[qid] = min(Ans[qid], qym(x + 1, y + 1));
        }
      }
    }
  for (int(i) = 1; (i) <= (int)(Q); (i)++) {
    if (Ans[i] == (1 << 30))
      printf("-1 ");
    else
      printf("%d ", ynk[Ans[i]]);
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain();
  }
  return 0;
}
