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>
struct com {
  long long x, y;
  inline com operator+(const com &a) { return {x + a.x, y + a.y}; }
  inline com operator-(const com &a) { return {x - a.x, y - a.y}; }
  inline com operator*(const com &a) { return {x * a.x, y * a.y}; }
  inline com operator%(const com &a) { return {x % a.x, y % a.y}; }
  inline bool operator==(const com &a) { return x == a.x && y == a.y; }
} pw[100002], ha[100002], hb[100002];
com operator*(int a, com b) { return {a * b.x, a * b.y}; }
const com bas = {233333, 233}, mod = {1234321237, 1000000007};
char a[100002], b[100002];
int N, M, Q, B, p[100002], w[100002];
bool cmp(int x, int y) {
  if (x == y) return 0;
  if (x > y) return !cmp(y, x);
  if (y - x > M)
    if (hb[M] * pw[x] % mod == (ha[x + M] - ha[x] + mod) % mod)
      if ((ha[y - M] - ha[x] + mod) * pw[M] % mod ==
          (ha[y] - ha[x + M] + mod) % mod)
        if ((ha[y] - ha[y - M] + mod) % mod == hb[M] * pw[y - M] % mod)
          return 1;
        else {
          int l = 0, r = M - 1;
          while (l < r) {
            int m = (l + r + 1) >> 1;
            if ((ha[y - M + m] - ha[y - M] + mod) % mod ==
                hb[m] * pw[y - M] % mod)
              l = m;
            else
              r = m - 1;
          }
          return a[y - M + l + 1] < b[l + 1];
        }
      else {
        int l = 0, r = y - M - x - 1;
        while (l < r) {
          int m = (l + r + 1) >> 1;
          if ((ha[x + m] - ha[x] + mod) * pw[M] % mod ==
              (ha[x + M + m] - ha[x + M] + mod) % mod)
            l = m;
          else
            r = m - 1;
        }
        return a[x + l + 1] < a[x + M + l + 1];
      }
    else {
      int l = 0, r = M - 1;
      while (l < r) {
        int m = (l + r + 1) >> 1;
        if (hb[m] * pw[x] % mod == (ha[x + m] - ha[x] + mod) % mod)
          l = m;
        else
          r = m - 1;
      }
      return b[l + 1] < a[x + l + 1];
    }
  else if (hb[y - x] * pw[x] % mod == (ha[y] - ha[x] + mod) % mod)
    if ((hb[M] - hb[y - x] + mod) % mod == hb[M - y + x] * pw[y - x] % mod)
      if ((ha[y] - ha[x] + mod) * pw[M] % mod ==
          (hb[M] - hb[M - y + x] + mod) * pw[y] % mod)
        return 1;
      else {
        int l = 0, r = y - x - 1;
        while (l < r) {
          int m = (l + r + 1) >> 1;
          if ((ha[x + m] - ha[x] + mod) * pw[M] % mod ==
              (hb[M - y + x + m] - hb[M - y + x] + mod) * pw[y] % mod)
            l = m;
          else
            r = m - 1;
        }
        return a[x + l + 1] < b[M - y + x + l + 1];
      }
    else {
      int l = 0, r = M - y + x - 1;
      while (l < r) {
        int m = (l + r + 1) >> 1;
        if ((hb[y - x + m] - hb[y - x] + mod) % mod == hb[m] * pw[y - x] % mod)
          l = m;
        else
          r = m - 1;
      }
      return b[y - x + l + 1] < b[l + 1];
    }
  else {
    int l = 0, r = y - x - 1;
    while (l < r) {
      int m = (l + r + 1) >> 1;
      if (hb[m] * pw[x] % mod == (ha[x + m] - ha[x] + mod) % mod)
        l = m;
      else
        r = m - 1;
    }
    return b[l + 1] < a[x + l + 1];
  }
}
void makep() {
  scanf("%s%s%d", a + 1, b + 1, &Q);
  while (a[N + 1]) N++;
  while (b[M + 1]) M++;
  B = N == 1 ? 1 : sqrt(N / log(N)) * 1.8;
  if (B > N) B = N;
  if (B < 1) B = 1;
  pw[0] = {1, 1};
  for (int i = 1; i <= N || i <= M; i++) pw[i] = pw[i - 1] * bas % mod;
  for (int i = 1; i <= N; i++)
    ha[i] = (ha[i - 1] + a[i] * pw[i]) % mod, p[i] = i;
  for (int i = 1; i <= M; i++) hb[i] = (hb[i - 1] + b[i] * pw[i]) % mod;
  std::sort(p, p + N + 1, cmp);
  for (int i = 0; i <= N; i++) w[p[i]] = i;
}
int rmq[18][100002], Log[100002], LOG, ql[100002], qr[100002], qk[100002],
    qx[100002], qy[100002], O[100002];
std::vector<int> V[100002];
inline int low(int x, int y) { return x < 0 ? (x - y + 1) / y : x / y; }
void solve(int k) {
  LOG = Log[N / k + 1];
  for (int i = 0; i <= N; i++) rmq[0][i] = w[i];
  for (int i = 1; i <= LOG; i++)
    for (int j = 0; j <= N - (k << i) + k; j++)
      rmq[i][j] = std::min(rmq[i - 1][j], rmq[i - 1][j + (k << i >> 1)]);
  for (auto &id : V[k]) {
    int l = ql[id], r = qr[id], x = qx[id], y = qy[id];
    for (int i = x; i <= y; i++) {
      int L = (l - i + k - 1) / k, R = (r - i) / k;
      if (L <= R) {
        int lg = Log[R - L + 1];
        O[id] = std::min(O[id], std::min(rmq[lg][L * k + i],
                                         rmq[lg][(R - (1 << lg) + 1) * k + i]));
      }
    }
  }
}
void force(int id) {
  int l = ql[id], r = qr[id], k = qk[id], x = qx[id], y = qy[id];
  for (int i = 0; i <= N; i += k) {
    int L = std::max(l, i + x), R = std::min(r, i + y);
    if (L <= R) {
      int lg = Log[R - L + 1];
      O[id] = std::min(O[id], std::min(rmq[lg][L], rmq[lg][R - (1 << lg) + 1]));
    }
  }
}
int main() {
  makep();
  for (int i = 2; i <= N + 1; i++) Log[i] = Log[i >> 1] + 1;
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d%d%d%d", ql + i, qr + i, qk + i, qx + i, qy + i);
    V[qk[i]].push_back(i);
    O[i] = 1000000;
  }
  for (int i = 1; i <= B; i++)
    if (V[i].size()) solve(i);
  LOG = Log[N + 1];
  for (int i = 0; i <= N; i++) rmq[0][i] = w[i];
  for (int i = 1; i <= LOG; i++)
    for (int j = 0; j <= N - (1 << i) + 1; j++)
      rmq[i][j] = std::min(rmq[i - 1][j], rmq[i - 1][j + (1 << i >> 1)]);
  for (int i = B + 1; i <= N; i++)
    for (auto &j : V[i]) force(j);
  for (int i = 1; i <= Q; i++)
    printf("%d%c", O[i] == 1000000 ? -1 : p[O[i]], " \n"[i == Q]);
  return 0;
}
