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;
int logar2[400000];
void precLogar2() {
  for (int i = 2; i < 400000 - 5; ++i) logar2[i] = 1 + logar2[i >> 1];
}
struct RangeMinimumQuery {
  int n;
  int **table;
  int dims = -1;
  vector<int> a;
  RangeMinimumQuery(int n) : n(n) {
    a.clear();
    for (int i = 0; i <= dims; i++) delete table[i];
    delete table;
    dims = 0;
  };
  RangeMinimumQuery(){};
  void init() {
    a.clear();
    for (int i = 0; i <= dims; i++) delete table[i];
    delete table;
    dims = 0;
  }
  void Push(int x) { a.push_back(x); }
  void buildtable() {
    n = (int)a.size();
    dims = logar2[a.size()];
    if ((1 << dims) < a.size()) ++dims;
    table = new int *[dims + 1];
    for (int i = 0; i <= dims; ++i) {
      table[i] = new int[n];
    }
    for (int i = 0; i < n; ++i) table[0][i] = a[i];
    for (int j = 1; (1 << j) <= n; j++) {
      for (int i = 0; i <= n - (1 << j); i++) {
        int tem = min(table[j - 1][i], table[j - 1][i + (1 << (j - 1))]);
        table[j][i] = tem;
      }
    }
    return;
  }
  int RMQ(int L, int R) {
    int j = (int)log2(R - L + 1);
    if (table[j][L] <= table[j][R - (1 << j) + 1])
      return table[j][L];
    else
      return table[j][R - (1 << j) + 1];
  }
};
const int MAX = 300100;
char txt[MAX];
int iSA[MAX], SA[MAX];
int cnt[MAX], nxt[MAX];
bool bh[MAX], b2h[MAX];
bool smaller_first_char(int a, int b) { return txt[a] < txt[b]; }
void suffixSort(int n) {
  for (int i = 0; i < n; ++i) {
    SA[i] = i;
  }
  sort(SA, SA + n, smaller_first_char);
  for (int i = 0; i < n; ++i) {
    bh[i] = i == 0 || txt[SA[i]] != txt[SA[i - 1]];
    b2h[i] = false;
  }
  for (int h = 1; h < n; h <<= 1) {
    int buckets = 0;
    for (int i = 0, j; i < n; i = j) {
      j = i + 1;
      while (j < n && !bh[j]) j++;
      nxt[i] = j;
      buckets++;
    }
    if (buckets == n) break;
    for (int i = 0; i < n; i = nxt[i]) {
      cnt[i] = 0;
      for (int j = i; j < nxt[i]; ++j) {
        iSA[SA[j]] = i;
      }
    }
    cnt[iSA[n - h]]++;
    b2h[iSA[n - h]] = true;
    for (int i = 0; i < n; i = nxt[i]) {
      for (int j = i; j < nxt[i]; ++j) {
        int s = SA[j] - h;
        if (s >= 0) {
          int head = iSA[s];
          iSA[s] = head + cnt[head]++;
          b2h[iSA[s]] = true;
        }
      }
      for (int j = i; j < nxt[i]; ++j) {
        int s = SA[j] - h;
        if (s >= 0 && b2h[iSA[s]]) {
          for (int k = iSA[s] + 1; !bh[k] && b2h[k]; k++) b2h[k] = false;
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      SA[iSA[i]] = i;
      bh[i] |= b2h[i];
    }
  }
  for (int i = 0; i < n; ++i) {
    iSA[SA[i]] = i;
  }
}
int lcp[MAX];
void getlcp(int n) {
  for (int i = 0; i < n; ++i) iSA[SA[i]] = i;
  lcp[0] = 0;
  for (int i = 0, h = 0; i < n; ++i) {
    if (iSA[i] > 0) {
      int j = SA[iSA[i] - 1];
      while (i + h < n && j + h < n && txt[i + h] == txt[j + h]) h++;
      lcp[iSA[i]] = h;
      if (h > 0) h--;
    }
  }
}
int n, m;
char a[400000];
char b[400000];
RangeMinimumQuery Sa;
int getCommon(int l, int r) {
  l--;
  r--;
  l = iSA[l];
  r = iSA[r];
  if (l > r) swap(l, r);
  int ret = Sa.RMQ(l + 1, r);
  return ret;
}
inline bool comp(int i, int j) {
  int temi = i;
  int temj = j;
  if (i > j) {
    return !comp(j, i);
  }
  int len = min(j - i, m);
  int mtch = getCommon(i + 1, n + 1);
  if (len > mtch) {
    return iSA[n] < iSA[i];
  }
  if (len == j - i) {
    mtch = getCommon(n + len + 1, n + 1);
    int len1 = m - len;
    if (mtch < len1) {
      return iSA[n + len] < iSA[n];
    }
    mtch = getCommon(n + len1 + 1, i + 1);
    int len2 = m - len1;
    if (mtch < len2) {
      return iSA[i] < iSA[n + len1];
    }
    return temi < temj;
  }
  mtch = getCommon(i + 1, i + len + 1);
  int len1 = j - i - len;
  if (mtch < len1) {
    return iSA[i] < iSA[i + len];
  }
  mtch = getCommon(n + 1, i + len1 + 1);
  int len2 = m;
  if (mtch < len2) {
    return iSA[i + len1] < iSA[n];
  }
  return temi < temj;
}
int arr[400000];
struct st {
  int l, r, x, y, id;
};
vector<st> smallQueries[350];
int ans[400000];
int inv[400000 + 5];
RangeMinimumQuery Choto[350];
inline void solve() {
  for (int i = 1; i <= 100; i++) {
    if (smallQueries[i].empty()) continue;
    for (int j = 0; j < n + 1; j++) {
      Choto[j % i].Push(inv[j]);
    }
    for (int j = 0; j < i; j++) Choto[j].buildtable();
    for (st u : smallQueries[i]) {
      ans[u.id] = INT_MAX;
      for (int j = u.x; j <= u.y; j++) {
        int l = u.l / i;
        int r = u.r / i;
        if (u.l % i > j) l++;
        if (u.r % i < j) r--;
        if (l <= r) ans[u.id] = min(ans[u.id], Choto[j].RMQ(l, r));
      }
    }
    for (int j = 0; j < i; j++) {
      Choto[j].init();
    }
  }
}
int main() {
  precLogar2();
  scanf("%s", a);
  scanf("%s", b);
  n = strlen(a);
  m = strlen(b);
  for (int i = 0; i < n; i++) txt[i] = a[i];
  for (int i = 0; i < m; i++) txt[n + i] = b[i];
  suffixSort(n + m);
  getlcp(n + m);
  for (int i = 0; i < n + m; i++) Sa.Push(lcp[i]);
  Sa.buildtable();
  for (int i = 0; i < n + m; i++) {
    arr[i] = i;
  }
  sort(arr, arr + n + 1, comp);
  Sa.init();
  int q;
  scanf("%d", &q);
  for (int i = 0; i <= n; i++) {
    inv[arr[i]] = i;
  }
  RangeMinimumQuery Boro;
  for (int i = 0; i <= n; i++) {
    Boro.Push(inv[i]);
  }
  Boro.buildtable();
  for (int t = 1; t <= q; t++) {
    int l, r, x, y, k;
    scanf("%d %d", &l, &r);
    scanf("%d", &k);
    scanf("%d %d", &x, &y);
    if (k <= 100) {
      smallQueries[k].push_back({l, r, x, y, t});
    } else {
      ans[t] = INT_MAX;
      for (int i = 0; i <= n; i += k) {
        int u = i + x;
        int v = i + y;
        if (u >= l && v <= r) {
          ans[t] = min(ans[t], Boro.RMQ(u, v));
        } else if (u > r || v < l)
          continue;
        else {
          u = max(u, l);
          v = min(v, r);
          ans[t] = min(ans[t], Boro.RMQ(u, v));
        }
      }
    }
  }
  solve();
  for (int i = 1; i <= q; i++) {
    if (i != 1) printf(" ");
    if (ans[i] == INT_MAX)
      printf("-1");
    else
      printf("%d", arr[ans[i]]);
  }
  printf("\n");
  return 0;
}
