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>
const int Mod = 1001943197;
const int Base = 34300;
const int MN = 100005, MQ = 100005, S = 500, MS = S + 5;
char s[MN], t[MN];
int N, lt, Lim, per[MN];
int pBase[MN];
int Hs[MN], Ht[MN];
inline int Hmerge(int h1, int h2, int l2) {
  return (int)(((long long)h1 * pBase[l2] + h2) % Mod);
}
inline int gHash(int *H, int lb, int rb) {
  return (int)(((long long)H[lb - 1] * (Mod - pBase[rb - lb + 1]) + H[rb]) %
               Mod);
}
inline bool smallerThan(int pos1, int pos2) {
  if (pos1 == pos2) return false;
  bool rev = false;
  if (pos1 > pos2) std::swap(pos1, pos2), rev = true;
  int lb = 0, rb = lt + (pos2 - pos1), ans = -1;
  while (lb <= rb) {
    int mid = (lb + rb) / 2;
    int hs1 = mid <= lt ? gHash(Ht, 1, mid)
                        : Hmerge(Ht[lt], gHash(Hs, pos1 + 1, pos1 + (mid - lt)),
                                 mid - lt);
    int hs2 = mid <= pos2 - pos1 ? gHash(Hs, pos1 + 1, pos1 + mid)
                                 : Hmerge(gHash(Hs, pos1 + 1, pos2),
                                          gHash(Ht, 1, mid - (pos2 - pos1)),
                                          mid - (pos2 - pos1));
    if (hs1 == hs2)
      ans = mid, lb = mid + 1;
    else
      rb = mid - 1;
  }
  if (ans == lt + (pos2 - pos1)) return rev ? pos2 < pos1 : pos1 < pos2;
  char ch1 = ans < lt ? t[ans + 1] : s[pos1 + ans - lt + 1];
  char ch2 = ans < pos2 - pos1 ? s[pos1 + ans + 1] : t[ans - (pos2 - pos1) + 1];
  if (rev) std::swap(ch1, ch2);
  return ch1 < ch2;
}
int iper[MN], id[MN];
int ST[17][MN];
inline int gMin(int x, int y) { return iper[x] < iper[y] ? x : y; }
inline int RMQ(int l, int r) {
  int j = 31 - __builtin_clz(r - l + 1);
  return gMin(ST[j][l + (1 << j) - 1], ST[j][r]);
}
int Q, ql[MQ], qr[MQ], qk[MQ], qx[MQ], qy[MQ], Ans[MQ];
std::vector<int> V[MS];
int main() {
  scanf("%s%s%d", s + 1, t + 1, &Q);
  N = (int)(strlen(s + 1)), lt = (int)(strlen(t + 1));
  for (int i = 1; i <= N; ++i)
    Hs[i] = (int)(((long long)Hs[i - 1] * Base + (s[i] - 'a' + 1)) % Mod);
  for (int i = 1; i <= lt; ++i)
    Ht[i] = (int)(((long long)Ht[i - 1] * Base + (t[i] - 'a' + 1)) % Mod);
  Lim = std::max(N, lt), pBase[0] = 1;
  for (int i = 1; i <= Lim; ++i)
    pBase[i] = (int)((long long)pBase[i - 1] * Base % Mod);
  for (int i = 1; i <= N + 1; ++i) per[i] = i - 1;
  std::sort(per + 1, per + N + 2, smallerThan);
  for (int i = 1; i <= N + 1; ++i) iper[per[i]] = i;
  for (int i = 0; i <= N; ++i) ST[0][i] = i;
  for (int j = 0; 2 << j <= N + 1; ++j)
    for (int i = (2 << j) - 1; i <= N; ++i)
      ST[j + 1][i] = gMin(ST[j][i - (1 << j)], ST[j][i]);
  for (int i = 1; i <= Q; ++i) {
    scanf("%d%d%d%d%d", &ql[i], &qr[i], &qk[i], &qx[i], &qy[i]);
    if (qk[i] > S) {
      int lim = N / qk[i], ans = -1;
      for (int j = 0; j <= lim; ++j) {
        int l = j * qk[i] + qx[i];
        int r = j * qk[i] + qy[i];
        l = std::max(l, ql[i]);
        r = std::min(r, qr[i]);
        if (l <= r) {
          int res = RMQ(l, r);
          if (ans == -1)
            ans = res;
          else
            ans = gMin(ans, res);
        }
      }
      Ans[i] = ans;
    } else
      V[qk[i]].push_back(i);
  }
  for (int k = 1; k <= S; ++k) {
    int tot = 0, mxlen = N / k + 1;
    for (int j = 0; j < k; ++j)
      for (int i = j; i <= N; i += k) ST[0][++tot] = i, id[i] = tot;
    for (int j = 0; 2 << j <= mxlen; ++j)
      for (int i = 2 << j; i <= tot; ++i)
        ST[j + 1][i] = gMin(ST[j][i - (1 << j)], ST[j][i]);
    for (int i : V[k]) {
      int ans = -1;
      for (int j = qx[i]; j <= qy[i]; ++j) {
        int l = id[j] + (ql[i] - j + k - 1) / k;
        int r = id[j] + (qr[i] - j + k) / k - 1;
        if (l <= r) {
          int res = RMQ(l, r);
          if (ans == -1)
            ans = res;
          else
            ans = gMin(ans, res);
        }
      }
      Ans[i] = ans;
    }
  }
  for (int i = 1; i <= Q; ++i) printf("%d%c", Ans[i], " \n"[i == Q]);
  return 0;
}
