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 read() {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  int x = 0;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
const int maxn = 100010;
const int maxd = 17;
const unsigned long long base = 23333;
const long long mod = 1e9 + 7;
const int INF = 1 << 30;
char s[maxn], t[maxn];
unsigned long long num[maxn], sum_s[maxn], sum_t[maxn];
long long num2[maxn], sum_s2[maxn], sum_t2[maxn];
int qcnt, len_s, len_t, p[maxn], val[maxn], lg[maxn];
void init() {
  num[0] = 1;
  for (register int i = 1; i < maxn; ++i) num[i] = num[i - 1] * base;
  sum_s[0] = s[0];
  for (register int i = 1; i < len_s; ++i)
    sum_s[i] = sum_s[i - 1] * base + s[i];
  sum_t[0] = t[0];
  for (register int i = 1; i < len_t; ++i)
    sum_t[i] = sum_t[i - 1] * base + t[i];
  num2[0] = 1;
  for (register int i = 1; i < maxn; ++i) num2[i] = num2[i - 1] * base % mod;
  sum_s2[0] = s[0];
  for (register int i = 1; i < len_s; ++i)
    sum_s2[i] = (sum_s2[i - 1] * base % mod + s[i]) % mod;
  sum_t2[0] = t[0];
  for (register int i = 1; i < len_t; ++i)
    sum_t2[i] = (sum_t2[i - 1] * base % mod + t[i]) % mod;
}
unsigned long long get_val(int pos, int len) {
  if (len <= pos) return sum_s[len - 1];
  unsigned long long val = (pos ? sum_s[pos - 1] : 0);
  if (len <= pos + len_t) return val * num[len - pos] + sum_t[len - pos - 1];
  val = val * num[len_t] + sum_t[len_t - 1];
  return val * num[len - len_t - pos] +
         (sum_s[len - len_t - 1] -
          (pos ? sum_s[pos - 1] * num[len - len_t - pos] : 0));
}
long long get_val2(int pos, int len) {
  if (len <= pos) return sum_s2[len - 1];
  long long val = (pos ? sum_s2[pos - 1] : 0);
  if (len <= pos + len_t)
    return (val * num2[len - pos] + sum_t2[len - pos - 1]) % mod;
  val = (val * num2[len_t] + sum_t2[len_t - 1]) % mod;
  long long ans = (val * num2[len - len_t - pos] +
                   (sum_s2[len - len_t - 1] -
                    (pos ? sum_s2[pos - 1] * num2[len - len_t - pos] : 0))) %
                  mod;
  ans = (ans % mod + mod) % mod;
  return ans;
}
char get_pos(int pos, int len) {
  if (len <= pos) return s[len - 1];
  if (len <= pos + len_t) return t[len - pos - 1];
  return s[len - len_t - 1];
}
bool cmp(int p1, int p2) {
  unsigned long long val1 = get_val(p1, len_s + len_t),
                     val2 = get_val(p2, len_s + len_t);
  long long val11 = get_val2(p1, len_s + len_t),
            val22 = get_val2(p2, len_s + len_t);
  if (val11 == val22) return p1 < p2;
  int l = 0, r = len_s + len_t;
  while (l < r - 1) {
    int mid = (l + r) >> 1;
    if (get_val(p1, mid) == get_val(p2, mid)) {
      if (get_val2(p1, mid) == get_val2(p2, mid))
        l = mid;
      else
        r = mid;
    } else
      r = mid;
  }
  return get_pos(p1, l + 1) < get_pos(p2, l + 1);
}
struct st_all {
  int mn[maxn][maxd];
  void build(int n) {
    for (int i = 0; i < n; ++i) mn[i][0] = val[i];
    for (int j = 1; j < maxd; ++j)
      for (int i = 1; i < n; ++i)
        if (i + (1 << j) - 1 < n)
          mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
  }
  int query(int l, int r) {
    int k = lg[r - l + 1];
    return min(mn[l][k], mn[r - (1 << k) + 1][k]);
  }
} rmq_all;
struct node {
  vector<int> pos, mn[maxd];
  void init() {
    pos.clear();
    for (int i = 0; i < maxd; ++i) mn[i].clear();
  }
} z[320];
int rt[320][320], treesize;
void insert(int a, int v) { z[a].pos.push_back(v); }
void upd_node(int a) {
  sort(z[a].pos.begin(), z[a].pos.end());
  for (int i = 0; i < z[a].pos.size(); ++i)
    z[a].mn[0].push_back(val[z[a].pos[i]]);
  int sz = z[a].pos.size();
  int k = lg[sz];
  for (int j = 1; j <= k; ++j)
    for (int i = 0; i < sz; ++i)
      if (i + (1 << j) - 1 < sz)
        z[a].mn[j].push_back(
            min(z[a].mn[j - 1][i], z[a].mn[j - 1][i + (1 << (j - 1))]));
}
int query(int a, int vl, int vr) {
  if (!z[a].pos.size()) return INF;
  if (z[a].pos[0] > vr) return INF;
  if (z[a].pos[z[a].pos.size() - 1] < vl) return INF;
  int p1 = lower_bound(z[a].pos.begin(), z[a].pos.end(), vl) - z[a].pos.begin();
  int p2 = upper_bound(z[a].pos.begin(), z[a].pos.end(), vr) - z[a].pos.begin();
  --p2;
  if (p1 > p2) return INF;
  int k = lg[p2 - p1 + 1];
  return min(z[a].mn[k][p1], z[a].mn[k][p2 - (1 << k) + 1]);
}
int ww[maxn], rr[maxn][4];
vector<int> kq[320];
int main() {
  for (int i = 0; i < maxd; ++i) {
    int sz = min(maxn, 1 << (i + 1));
    for (int j = (1 << i); j < sz; ++j) lg[j] = i;
  }
  scanf("%s%s%d", s, t, &qcnt);
  len_s = strlen(s), len_t = strlen(t);
  init();
  for (int i = 0; i <= len_s; ++i) p[i] = i;
  sort(p, p + len_s + 1, cmp);
  for (int i = 0; i <= len_s; ++i) val[p[i]] = i;
  rmq_all.build(len_s + 1);
  int mxk = (int)sqrt(len_s);
  int l, r, k, x, y;
  for (int now = 0; now < qcnt; ++now) {
    l = read(), r = read(), k = read(), x = read(), y = read();
    if (k <= mxk) {
      rr[now][0] = l;
      rr[now][1] = r;
      rr[now][2] = x;
      rr[now][3] = y;
      kq[k].push_back(now);
    } else {
      int ans = INF;
      for (int i = x; i <= len_s; i += k) {
        int curl = i, curr = min(len_s, i + y - x);
        if (curl > r || curr < l) continue;
        ans = min(ans, rmq_all.query(max(curl, l), min(curr, r)));
      }
      ww[now] = (ans < INF ? p[ans] : -1);
    }
  }
  for (int k = 1; k <= mxk; ++k) {
    if (!kq[k].size()) continue;
    for (int j = 0; j < k; ++j) z[j].init();
    for (int j = 0; j <= len_s; ++j) insert(j % k, j);
    for (int j = 0; j < k; ++j) upd_node(j);
    for (int now = 0; now < kq[k].size(); ++now) {
      int x = rr[kq[k][now]][2], y = rr[kq[k][now]][3], l = rr[kq[k][now]][0],
          r = rr[kq[k][now]][1];
      int ans = INF;
      for (int i = x; i <= y; ++i) ans = min(ans, query(i, l, r));
      ww[kq[k][now]] = (ans < INF ? p[ans] : -1);
    }
  }
  for (int i = 0; i < qcnt; ++i) printf("%d ", ww[i]);
  return 0;
}
