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 mod = 1000000009;
const int maxn = 100100;
char stra[maxn], strb[maxn];
int la, lb;
long long mi[maxn * 2];
long long ha[maxn], hb[maxn];
void dohash(long long *arr, char *str, int l) {
  for (int i = 0; i < l; i++) {
    arr[i + 1] = arr[i] + (str[i] - 'a') * mi[i];
    arr[i + 1] %= mod;
  }
}
inline long long gethash(int no, int l) {
  if (l <= no) return ha[l];
  long long ans = ha[no];
  if (l <= no + lb) {
    return (ans + mi[no] * hb[l - no]) % mod;
  }
  ans = (ans + mi[no] * hb[lb]) % mod;
  ans = (ans + mi[lb] * (ha[l - lb] - ha[no])) % mod;
  if (ans < 0) ans += mod;
  return ans;
}
inline char getch(int no, int l) {
  if (l <= no) return stra[l - 1];
  if (l <= no + lb) return strb[l - no - 1];
  return stra[l - lb - 1];
}
bool cmp(const int &a, const int &b) {
  int be = 0, en = la + lb;
  while (be != en) {
    int mid = (be + en + 1) / 2;
    if (gethash(a, mid) == gethash(b, mid))
      be = mid;
    else
      en = mid - 1;
  }
  if (be == la + lb) return a < b;
  if (getch(a, be + 1) < getch(b, be + 1)) return 1;
  return 0;
}
bool cmp1(const int &a, const int &b) {
  string ta = string(stra, a) + string(strb) + string(stra + a);
  string tb = string(stra, b) + string(strb) + string(stra + b);
  return ta < tb;
}
int sa[maxn], rk[maxn];
pair<int, int> arr[maxn];
int d[20];
int logg[maxn];
pair<int, int> st[maxn][22];
void InitRMQ(const int &n) {
  int i, j;
  for (d[0] = 1, i = 1; i < 21; ++i) d[i] = 2 * d[i - 1];
  for (i = 0; i < n; ++i) st[i][0] = arr[i];
  int k = int(log(double(n)) / log(2)) + 1;
  logg[0] = 0;
  logg[1] = 0;
  for (int i = 2; i <= n; i++) logg[i] = logg[i / 2] + 1;
  for (j = 1; j < k; ++j)
    for (i = 0; i < n; ++i) {
      if (i + d[j - 1] - 1 < n) {
        st[i][j] = min(st[i][j - 1], st[i + d[j - 1]][j - 1]);
      } else
        break;
    }
}
inline pair<int, int> quemin(int x, int y) {
  int k = logg[y - x + 1];
  return min(st[x][k], st[y - d[k] + 1][k]);
}
inline void upd(int &a, int b) {
  if (rk[a] > rk[b]) a = b;
}
int nq;
int q[maxn][5];
int cate[maxn];
int ans[maxn];
vector<int> need[110];
int main() {
  scanf("%s%s", stra, strb);
  la = strlen(stra), lb = strlen(strb);
  for (int i = 0; i <= la; i++) sa[i] = i;
  mi[0] = 1;
  for (int i = 1; i < maxn * 2; i++) mi[i] = mi[i - 1] * 26 % mod;
  dohash(ha, stra, la);
  dohash(hb, strb, lb);
  sort(sa, sa + la + 1, cmp);
  for (int i = 0; i <= la; i++) rk[sa[i]] = i;
  scanf("%d", &nq);
  for (int i = 0; i < nq; i++) {
    for (int j = 0; j < 5; j++) scanf("%d", q[i] + j);
    if (q[i][1] / q[i][2] - q[i][0] / q[i][2] > 1000) {
      cate[i] = 1;
      need[q[i][2]].push_back(i);
    }
  }
  for (int i = 0; i <= la; i++) arr[sa[i]] = make_pair(i, sa[i]);
  InitRMQ(la + 1);
  sa[la + 1] = la + 10;
  rk[la + 1] = la + 10;
  for (int i = 0; i < nq; i++)
    if (!cate[i]) {
      ans[i] = la + 1;
      int k = q[i][2];
      for (int j = q[i][0] / k; j <= q[i][1] / k; j++) {
        int l = j * k + q[i][3], r = j * k + q[i][4];
        l = max(l, q[i][0]), r = min(r, q[i][1]);
        if (l <= r) upd(ans[i], quemin(l, r).second);
      }
    }
  for (int i = 1; i <= 100; i++)
    if (need[i].size()) {
      for (auto it : need[i]) ans[it] = la + 1;
      for (int j = 0; j < i; j++) {
        int larr = 0;
        for (int k = j; k < la + 1; k += i) arr[larr++] = make_pair(rk[k], k);
        InitRMQ(larr);
        for (auto it : need[i])
          if (j >= q[it][3] && j <= q[it][4]) {
            int l = q[it][0] / i * i + j, r = q[it][1] / i * i + j;
            if (l < q[it][0]) l += i;
            if (r > q[it][1]) r -= i;
            l = l / i, r = r / i;
            if (l <= r) upd(ans[it], quemin(l, r).second);
          }
      }
    }
  for (int i = 0; i < nq; i++) {
    if (ans[i] == la + 1) ans[i] = -1;
    printf("%d ", ans[i]);
  }
  puts("");
  return 0;
}
