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 = 1e9 + 7;
const int MUL1 = 137;
const int MUL2 = 131;
const int SIZE = 2e5 + 10;
long long mypow(long long x, long long y) {
  x %= MOD;
  long long res = 1 % MOD;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}
char s[SIZE];
int sn, tn;
pair<long long, long long> dp[SIZE];
pair<long long, long long> inv[SIZE], pwr[SIZE];
bool same(int st1, int st2, int len) {
  return ((dp[st1 + len - 1].first - dp[st1 - 1].first) * inv[st1].first -
          (dp[st2 + len - 1].first - dp[st2 - 1].first) * inv[st2].first) %
                 MOD ==
             0 &&
         ((dp[st1 + len - 1].second - dp[st1 - 1].second) * inv[st1].second -
          (dp[st2 + len - 1].second - dp[st2 - 1].second) * inv[st2].second) %
                 MOD ==
             0;
}
int compare_substring(int st1, int st2, int len) {
  int ll = 0, rr = len;
  while (ll < rr) {
    int mm = (ll + rr + 1) / 2;
    if (same(st1, st2, mm))
      ll = mm;
    else
      rr = mm - 1;
  }
  if (ll == len) return 0;
  if (s[st1 + ll] < s[st2 + ll]) return 1;
  return -1;
}
int compare2(pair<int, int> d[][2]) {
  int it1 = 0, it2 = 0;
  while (it1 < 2 && it2 < 2) {
    if (d[0][it1].first == d[0][it1].second) {
      it1++;
      continue;
    }
    if (d[1][it2].first == d[1][it2].second) {
      it2++;
      continue;
    }
    int mi = min(d[0][it1].second - d[0][it1].first,
                 d[1][it2].second - d[1][it2].first);
    int ret = compare_substring(d[0][it1].first, d[1][it2].first, mi);
    if (ret > 0) return 1;
    if (ret < 0) return -1;
    d[0][it1].first += mi;
    d[1][it2].first += mi;
  }
  return 0;
}
bool compare(int x, int y) {
  x++;
  y++;
  if (x < y) {
    pair<int, int> d[2][2];
    d[0][0] = make_pair(sn + 1, sn + tn + 1);
    d[0][1] = make_pair(x, y);
    d[1][0] = make_pair(x, y);
    d[1][1] = make_pair(sn + 1, sn + tn + 1);
    int ret = compare2(d);
    return ret >= 0;
  } else {
    swap(x, y);
    pair<int, int> d[2][2];
    d[1][0] = make_pair(sn + 1, sn + tn + 1);
    d[1][1] = make_pair(x, y);
    d[0][0] = make_pair(x, y);
    d[0][1] = make_pair(sn + 1, sn + tn + 1);
    int ret = compare2(d);
    return ret > 0;
  }
}
void build() {
  int stn = sn + tn;
  pwr[0] = inv[0] = make_pair(1, 1);
  for (int i = (1); i < (stn + 1); ++i) {
    pwr[i] = make_pair(pwr[i - 1].first * MUL1 % MOD,
                       pwr[i - 1].second * MUL2 % MOD);
  }
  inv[1] = make_pair(mypow(MUL1, MOD - 2), mypow(MUL2, MOD - 2));
  for (int i = (2); i < (stn + 1); ++i) {
    inv[i] = make_pair(inv[i - 1].first * inv[1].first % MOD,
                       inv[i - 1].second * inv[1].second % MOD);
  }
  for (int i = (1); i < (stn + 1); ++i) {
    dp[i] = make_pair((dp[i - 1].first + pwr[i].first * s[i]) % MOD,
                      (dp[i - 1].second + pwr[i].second * s[i]) % MOD);
  }
}
int sorted_list[SIZE];
int ord[SIZE];
int an[SIZE];
vector<int> qq[SIZE];
const int BB = 250;
int rmq_mi[17][SIZE], to[SIZE], now_mod;
int l[SIZE], r[SIZE], xx[SIZE], yy[SIZE];
void build_rmq(int mod, int r) {
  now_mod = mod;
  int dn = 0;
  while (r <= sn) {
    rmq_mi[0][dn++] = ord[r];
    r += mod;
  }
  for (int i = (1); i < (17); ++i) {
    for (int j = 0; j + (1 << i) <= dn; j++) {
      rmq_mi[i][j] = min(rmq_mi[i - 1][j], rmq_mi[i - 1][j + (1 << (i - 1))]);
    }
  }
}
int qq_rmq(int L, int R) {
  int n = R - L + 1;
  int lv = to[n];
  return min(rmq_mi[lv][L], rmq_mi[lv][R - (1 << lv) + 1]);
}
void solve(int mod) {
  if (((int)(qq[mod]).size()) == 0) return;
  if (mod == 1 || mod >= BB) {
    if (now_mod != 1) build_rmq(1, 0);
    for (int i = 0; i < (((int)(qq[mod]).size())); ++i) {
      int id = qq[mod][i];
      int now_l = xx[id], now_r = yy[id];
      while (now_r < l[id]) {
        now_l += mod;
        now_r += mod;
      }
      while (now_l <= r[id]) {
        an[id] = min(an[id], qq_rmq(max(l[id], now_l), min(r[id], now_r)));
        now_l += mod;
        now_r += mod;
      }
    }
  } else {
    for (int r2 = 0; r2 < (mod); ++r2) {
      build_rmq(mod, r2);
      for (int i = 0; i < (((int)(qq[mod]).size())); ++i) {
        int id = qq[mod][i];
        if (xx[id] > r2 || yy[id] < r2) continue;
        int ll = l[id] / mod * mod + r2;
        while (ll < l[id]) ll += mod;
        int rr = r[id] / mod * mod + r2;
        while (rr > r[id]) rr -= mod;
        while (rr + mod <= r[id]) rr += mod;
        if (ll <= rr) an[id] = min(an[id], qq_rmq(ll / mod, rr / mod));
      }
    }
  }
}
int main() {
  for (int i = 0; i < (17); ++i) {
    for (int j = (1); j < (SIZE); ++j) {
      if ((1 << i) <= j) to[j] = i;
    }
  }
  scanf("%s", (s + 1));
  sn = strlen(s + 1);
  scanf("%s", (s + 1 + sn));
  tn = strlen(s + 1 + sn);
  int(q);
  scanf("%d", &q);
  build();
  for (int i = 0; i < (sn + 1); ++i) sorted_list[i] = i;
  sort(sorted_list, sorted_list + sn + 1, compare);
  for (int i = 0; i < (sn + 1); ++i) ord[sorted_list[i]] = i;
  for (int i = 0; i < (q); ++i) {
    an[i] = MOD;
    scanf("%d%d", &(l[i]), &(r[i]));
    int(K);
    scanf("%d", &K);
    qq[K].push_back(i);
    scanf("%d%d", &(xx[i]), &(yy[i]));
  }
  for (int i = (2); i < (sn + 1); ++i) {
    solve(i);
  }
  solve(1);
  for (int i = 0; i < (q); ++i) {
    if (an[i] == MOD)
      puts("-1");
    else
      printf("%d\n", sorted_list[an[i]]);
  }
  return 0;
}
