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 long long mod1 = 1LL * 1000000007 * 1000000007,
                mod2 = 1LL * 1000000009 * 1000000009;
int pos = 1 << 17;
char buf[1 << 17];
std::vector<int> *remechiu[65 + 1][16 + 1], *rmqSef[16 + 1], mare,
    queries[65 + 1];
int s[2 * 100009], v[100009];
int ans[100009], lung[65 + 1];
int lg[2 * 100009], ind[100009];
int l[100009], r[100009], k[100009], first[100009], second[100009];
std::pair<int, int> h[2 * 100009], pb[2 * 100009];
int N, M, T;
inline char nextch() {
  if (pos == 1 << 17) fread(buf, 1 << 17, 1, stdin), pos = 0;
  return buf[pos++];
}
inline int read() {
  int first = 0;
  char ch = nextch();
  while (!isdigit(ch)) ch = nextch();
  while (isdigit(ch)) {
    first = 10 * first + ch - '0';
    ch = nextch();
  }
  return first;
}
inline std::pair<int, int> getHash(int a, int b) {
  if (a > b) return std::make_pair(0, 0);
  if (a == 0)
    return h[b];
  else
    return std::make_pair(
        (h[b].first - 1LL * h[a - 1].first * pb[b - a + 1].first + mod1) %
            1000000007,
        (h[b].second - 1LL * h[a - 1].second * pb[b - a + 1].second + mod2) %
            1000000009);
}
inline bool lcp(int a, int b) {
  int rez = 0;
  for (int pas = 1 << lg[std::min(M - a + 1, M - b + 1)]; pas; pas >>= 1)
    if ((a + rez + pas <= M) && (b + rez + pas <= M) &&
        (getHash(a, a + rez + pas - 1) == getHash(b, b + rez + pas - 1)))
      rez += pas;
  return s[a + rez] < s[b + rez];
}
bool cmp(const int &A, const int &B) {
  int a = A, b = B;
  bool q = 0;
  if (b < a) {
    int aux = a;
    a = b;
    b = aux;
    q = 1;
  }
  if (b >= a + T) {
    if (getHash(N + 1, M) != getHash(a + 1, a + T))
      return lcp(N + 1, a + 1) ^ q;
    else if (getHash(a + 1, b - T) != getHash(a + T + 1, b))
      return lcp(a + 1, a + T + 1) ^ q;
    else if (getHash(b - T + 1, b) != getHash(N + 1, M))
      return lcp(b - T + 1, N + 1) ^ q;
    else
      return A < B;
  } else {
    if (getHash(N + 1, N + b - a) != getHash(a + 1, b))
      return lcp(N + 1, a + 1) ^ q;
    else if (getHash(N + b - a + 1, M) != getHash(N + 1, M + a - b))
      return lcp(N + b - a + 1, N + 1) ^ q;
    else if (getHash(a + 1, b) != getHash(M + a - b + 1, M))
      return lcp(a + 1, M + a - b + 1) ^ q;
    else
      return A < B;
  }
}
inline void calc(int n, int m) {
  pb[0] = std::make_pair(1, 1);
  for (int i = 1; i <= m; i++) {
    h[i].first = (1LL * h[i - 1].first * 666013 + s[i]) % 1000000007;
    h[i].second = (1LL * h[i - 1].second * 666019 + s[i]) % 1000000009;
    pb[i].first = (1LL * pb[i - 1].first * 666013) % 1000000007;
    pb[i].second = (1LL * pb[i - 1].second * 666019) % 1000000009;
  }
  for (int i = 0; i <= n; i++) ind[i] = i;
  N = n;
  M = m;
  T = m - n;
  std::sort(ind, ind + n + 1, cmp);
  for (int i = 0; i <= n; i++) v[ind[i]] = i;
}
bool compare(const int &a, const int &b) { return r[a] < r[b]; }
inline void update(int &first, int second) {
  if ((second != -1) && ((first == -1) || (v[second] < v[first])))
    first = second;
}
inline int query(std::vector<int> *v[], int first, int second) {
  if (first > second) return -1;
  int ans = (*v[lg[second - first + 1]])[second];
  update(
      ans,
      (*v[lg[second - first + 1]])[first + (1 << lg[second - first + 1]) - 1]);
  return ans;
}
inline void vine(int first, std::vector<int> *v[], int &r) {
  (*v[0])[r] = first;
  for (int i = 1; i <= lg[r + 1]; i++) {
    (*v[i])[r] = (*v[i - 1])[r];
    update((*v[i])[r], (*v[i - 1])[r - (1 << (i - 1))]);
  }
  r++;
}
inline void precalc(int n) {
  lg[0] = -1;
  for (int i = 2; i <= n + 1; i++) {
    lg[i] = lg[i - 1];
    if ((1 << (1 + lg[i])) == i) lg[i]++;
  }
}
inline void makeRmq(int n) {
  int first = 0;
  for (int i = 0; i <= lg[n + 1]; i++) rmqSef[i] = new std::vector<int>(n + 1);
  for (int i = 0; i <= n; i++) vine(i, rmqSef, first);
}
int main() {
  char ch = nextch();
  int n = 0;
  while (ch != ' ') {
    s[++n] = ch - 'a' + 1;
    ch = nextch();
  }
  ch = nextch();
  int m = n;
  while (ch != ' ') {
    s[++m] = ch - 'a' + 1;
    ch = nextch();
  }
  precalc(m);
  calc(n, m);
  makeRmq(n);
  int Q = read();
  for (int i = 0; i < Q; i++) {
    l[i] = read();
    r[i] = read();
    k[i] = read();
    first[i] = read();
    second[i] = read();
    ans[i] = -1;
    if ((first[i] == 0) && (second[i] == k[i] - 1))
      update(ans[i], query(rmqSef, l[i], r[i]));
    else if (k[i] > 65)
      mare.push_back(i);
    else
      queries[k[i]].push_back(i);
  }
  for (auto q : mare)
    for (int i = l[q] / k[q]; i <= r[q] / k[q]; i++)
      update(ans[q], query(rmqSef, std::max(l[q], i * k[q] + first[q]),
                           std::min(r[q], i * k[q] + second[q])));
  for (int kapa = 2; kapa <= 65; kapa++) {
    for (int i = 0; i < kapa; i++)
      for (int j = 0; j <= lg[(n + 1) / kapa + 2]; j++)
        remechiu[i][j] = new std::vector<int>((n + 1) / kapa + 2);
    std::sort(queries[kapa].begin(), queries[kapa].end(), compare);
    int poz = 0;
    for (auto q : queries[kapa]) {
      while (poz <= r[q]) {
        vine(poz, remechiu[poz % kapa], lung[poz % kapa]);
        poz++;
      }
      for (int i = first[q]; i <= second[q]; i++)
        update(ans[q], query(remechiu[i % kapa],
                             l[q] / kapa + (i < l[q] % kapa), lung[i] - 1));
    }
    for (int i = 0; i < kapa; i++) {
      for (int j = 0; j <= lg[(n + 1) / kapa + 1]; j++) delete remechiu[i][j];
      lung[i] = 0;
    }
  }
  for (int i = 0; i < Q; i++) fprintf(stdout, "%d ", ans[i]);
  fclose(stdin);
  fclose(stdout);
  return 0;
}
