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 maxN = 101000 * 2;
const int maxBit = 20;
const int maxSqrt = 300;
const int inf = 2147483647;
class Question {
 public:
  int l, r, x, y, id;
};
char S[maxN], T[maxN];
int L, L1, L2, SA[maxN], SSA[maxN], Rk[maxN], A[maxN], B[maxN], CA[maxN],
    CB[maxN], Height[maxBit][maxN];
int Lg2[maxN], Id[maxN], Sorter[maxN];
int Seq[maxBit][maxN], Ans[maxN];
vector<Question> Qn[maxN];
void GetSA();
int GetLcp(int u, int v);
bool cmp(int a, int b);
int GetMin(int l, int r);
int main() {
  for (int i = 1; i < maxN; i++) Lg2[i] = log2(i);
  scanf("%s", S + 1);
  scanf("%s", T + 1);
  L1 = strlen(S + 1);
  L2 = strlen(T + 1);
  L = L1 + L2;
  for (int i = 1; i <= L2; i++) S[L1 + i] = T[i];
  GetSA();
  for (int i = 0; i <= L1; i++) Sorter[i] = i;
  sort(&Sorter[0], &Sorter[L1 + 1], cmp);
  for (int i = 0; i <= L1; i++) Id[Sorter[i]] = i;
  for (int i = 0; i <= L1; i++) Seq[0][i] = Id[i];
  for (int i = 1; i < maxBit; i++)
    for (int j = 0; j + (1 << (i)) - 1 <= L1; j++)
      Seq[i][j] = min(Seq[i - 1][j], Seq[i - 1][j + (1 << (i - 1))]);
  int Q;
  scanf("%d", &Q);
  for (int qi = 1; qi <= Q; qi++) {
    int l, r, k, x, y;
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    Ans[qi] = inf;
    if (k == 1) Ans[qi] = min(Ans[qi], GetMin(l, r));
    if (k >= maxSqrt) {
      for (int i = x, j = y; i <= L1; i += k, j += k) {
        Ans[qi] = min(Ans[qi], GetMin(max(i, l), min(j, r)));
      }
    } else
      Qn[k].push_back((Question){l, r, x, y, qi});
  }
  for (int K = 2; K < maxSqrt; K++)
    if (Qn[K].size())
      for (int md = 0; md < K; md++) {
        int cnt = -1;
        for (int i = md; i <= L1; i += K) Seq[0][++cnt] = Id[i];
        for (int i = 1; i < maxBit; i++)
          for (int j = 0; j + (1 << (i)) - 1 <= cnt; j++)
            Seq[i][j] = min(Seq[i - 1][j], Seq[i - 1][j + (1 << (i - 1))]);
        for (int i = 0, sz = Qn[K].size(); i < sz; i++)
          if ((Qn[K][i].x <= md) && (Qn[K][i].y >= md)) {
            int L = Qn[K][i].l, R = Qn[K][i].r;
            if (L % K > md)
              L = L + K - (L % K - md);
            else
              L = L + md - L % K;
            if (R % K < md)
              R = R - K + md - R % K;
            else
              R = R - (R % K - md);
            if (L > R) continue;
            L = (L - md) / K;
            R = (R - md) / K;
            if (L <= R) Ans[Qn[K][i].id] = min(Ans[Qn[K][i].id], GetMin(L, R));
          }
      }
  for (int i = 1; i <= Q; i++)
    if (Ans[i] == inf)
      printf("-1 ");
    else
      printf("%d ", Sorter[Ans[i]]);
  return 0;
}
void GetSA() {
  for (int i = 1; i <= L; i++) CA[S[i]]++;
  for (int i = 1; i < maxN; i++) CA[i] += CA[i - 1];
  for (int i = L; i >= 1; i--) SA[CA[S[i]]--] = i;
  Rk[SA[1]] = 1;
  for (int i = 2; i <= L; i++) {
    Rk[SA[i]] = Rk[SA[i - 1]];
    if (S[SA[i]] != S[SA[i - 1]]) Rk[SA[i]]++;
  }
  for (int len = 1; Rk[SA[L]] != L; len <<= 1) {
    memset(CA, 0, sizeof(CA));
    memset(CB, 0, sizeof(CB));
    for (int i = 1; i <= L; i++)
      ++CA[A[i] = Rk[i]], ++CB[B[i] = (i + len <= L) ? Rk[i + len] : 0];
    for (int i = 1; i < maxN; i++) CA[i] += CA[i - 1], CB[i] += CB[i - 1];
    for (int i = L; i >= 1; i--) SSA[CB[B[i]]--] = i;
    for (int i = L; i >= 1; i--) SA[CA[A[SSA[i]]]--] = SSA[i];
    Rk[SA[1]] = 1;
    for (int i = 2; i <= L; i++) {
      Rk[SA[i]] = Rk[SA[i - 1]];
      if ((A[SA[i]] != A[SA[i - 1]]) || (B[SA[i]] != B[SA[i - 1]])) ++Rk[SA[i]];
    }
  }
  for (int i = 1, j = 0; i <= L; i++) {
    if (j) --j;
    while (S[i + j] == S[SA[Rk[i] - 1] + j]) ++j;
    Height[0][Rk[i]] = j;
  }
  for (int i = 1; i < 20; i++)
    for (int j = 1; j + (1 << (i - 1)) <= L; j++)
      Height[i][j] = min(Height[i - 1][j], Height[i - 1][j + (1 << (i - 1))]);
  return;
}
int GetLcp(int u, int v) {
  if (u == v) return L1 + L2 - u + 1;
  u = Rk[u];
  v = Rk[v];
  if (u > v) swap(u, v);
  ++u;
  int lg = Lg2[v - u + 1];
  return min(Height[lg][u], Height[lg][v - (1 << (lg)) + 1]);
}
bool cmp(int a, int b) {
  if (a == b) return 0;
  int lcp = 0, opt = (a > b);
  if (a > b) swap(a, b);
  if (b - a >= L2) {
    lcp = GetLcp(L1 + 1, a + 1);
    if (lcp < L2) return (S[L1 + 1 + lcp] < S[a + 1 + lcp]) ^ opt;
    lcp = GetLcp(a + 1, a + L2 + 1);
    if (lcp < b - L2 - a) return (S[a + 1 + lcp] < S[a + L2 + 1 + lcp]) ^ opt;
    lcp = GetLcp(b - L2 + 1, L1 + 1);
    if (lcp < L2) return (S[b - L2 + 1 + lcp] < S[L1 + 1 + lcp]) ^ opt;
    return opt ^ 1;
  } else {
    lcp = GetLcp(L1 + 1, a + 1);
    if (lcp < b - a) return (S[L1 + 1 + lcp] < S[a + 1 + lcp]) ^ opt;
    lcp = GetLcp(L1 + 1 + b - a, L1 + 1);
    if (lcp < a + L2 - b)
      return (S[L1 + 1 + b - a + lcp] < S[L1 + 1 + lcp]) ^ opt;
    lcp = GetLcp(a + 1, L1 + 1 + a + L2 - b);
    if (lcp < b - a)
      return (S[a + 1 + lcp] < S[L1 + 1 + a + L2 - b + lcp]) ^ opt;
  }
  return (a < b) ^ opt;
}
int GetMin(int l, int r) {
  if (l > r) return inf;
  int lg = Lg2[r - l + 1];
  return min(Seq[lg][l], Seq[lg][r - (1 << (lg)) + 1]);
}
