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 N = 100005, P = 998244353;
char s[N], t[N];
using ll = long long;
int q, ls, lt, c[N], rk[N];
ll pw[N], ht[N], hs[N];
ll calc(int p, int l) {
  if (l <= p) return hs[l];
  if (l <= p + lt) return (hs[p] * pw[l - p] + ht[l - p]) % P;
  return ((hs[p] * pw[l - p] + ht[lt] * pw[l - p - lt] + hs[l - lt] -
           hs[p] * pw[l - lt - p]) %
              P +
          P) %
         P;
}
inline int getc(int p, int l) {
  return l <= p ? s[l] : l <= p + lt ? t[l - p] : s[l - lt];
}
bool cmp(int a, int b) {
  int l = 0, r = ls + lt;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (calc(a, mid) == calc(b, mid))
      l = mid;
    else
      r = mid - 1;
  }
  return getc(a, l + 1) < getc(b, l + 1);
}
int l[N], r[N], kk[N], x[N], y[N], lg[N], ans[N];
vector<int> v[N];
vector<vector<int>> st;
bool cmp2(int a, int b) { return rk[a] < rk[b] || (rk[a] == rk[b] && a < b); }
int query(int a, int b) {
  if (a > b) return ls + 1;
  int k = lg[b - a + 1];
  return cmp2(st[k][a], st[k][b - (1 << k) + 1]) ? st[k][a]
                                                 : st[k][b - (1 << k) + 1];
}
int main() {
  ios::sync_with_stdio(false);
  cin >> (s + 1) >> (t + 1) >> q;
  ls = strlen(s + 1);
  lt = strlen(t + 1);
  for (int i = 1; i <= ls; i++) hs[i] = (hs[i - 1] * 100 + s[i]) % P;
  for (int i = 1; i <= lt; i++) ht[i] = (ht[i - 1] * 100 + t[i]) % P;
  pw[0] = 1;
  for (int i = 1; i <= ls + lt; i++) pw[i] = pw[i - 1] * 100 % P;
  for (int i = 0; i <= ls; i++) c[i] = i;
  sort(c, c + ls + 1, cmp);
  int cnt = 0;
  for (int i = 0; i <= ls; i++)
    if (!i || cmp(c[i - 1], c[i]))
      rk[c[i]] = ++cnt;
    else
      rk[c[i]] = cnt;
  st = vector<vector<int>>(17, vector<int>(ls + 1));
  for (int i = 0; i <= ls; i++) st[0][i] = i;
  for (int j = 1; j < 17; j++)
    for (int i = 0; i <= ls - (1 << j) + 1; i++)
      st[j][i] = cmp2(st[j - 1][i], st[j - 1][i + (1 << (j - 1))])
                     ? st[j - 1][i]
                     : st[j - 1][i + (1 << (j - 1))];
  for (int i = 2; i <= ls; i++) lg[i] = lg[i >> 1] + 1;
  rk[ls + 1] = INT_MAX;
  for (int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i] >> kk[i] >> x[i] >> y[i];
    ans[i] = ls + 1;
    if (kk[i] <= 100)
      v[kk[i]].push_back(i);
    else
      for (int j = 0; j * kk[i] + x[i] <= ls; j++)
        if (j * kk[i] + x[i] <= r[i] && j * kk[i] + y[i] >= l[i]) {
          int t =
              query(max(j * kk[i] + x[i], l[i]), min(j * kk[i] + y[i], r[i]));
          if (cmp2(t, ans[i])) ans[i] = t;
        }
  }
  for (int i = 1; i <= 100; i++)
    for (int j = 0; j < i; j++) {
      st = vector<vector<int>>(17, vector<int>(ls / i + 5));
      int idx = 0;
      while (i * idx + j <= ls) st[0][idx] = i * idx + j, ++idx;
      for (int k = 1; k < 17; k++)
        for (int p = 0; p <= idx - (1 << k) + 1; p++)
          st[k][p] = cmp2(st[k - 1][p], st[k - 1][p + (1 << (k - 1))])
                         ? st[k - 1][p]
                         : st[k - 1][p + (1 << (k - 1))];
      for (auto &vv : v[i])
        if (x[vv] <= j && j <= y[vv]) {
          int t = query(int(ceil((l[vv] - j + 0.0) / i)),
                        int(floor((r[vv] - j + 0.0) / i)));
          if (cmp2(t, ans[vv])) ans[vv] = t;
        }
    }
  for (int i = 1; i <= q; i++)
    if (ans[i] == ls + 1) ans[i] = -1;
  for (int i = 1; i <= q; i++) cout << ans[i] << ' ';
  return 0;
}
