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 inf = 213333333;
const int N = 200100;
int sa[N], tsa[N];
int rk[N], trk[N];
int sum[N], h[N];
int lg[N], ans[N];
int val[N], ord[N], id[N];
int n, m, q, len, kuai = 120;
int cm, cb, x, y, k, l, r;
char s[N], t[N];
struct node {
  int x, y, k, l, r, id;
  node(int _l = 0, int _r = 0, int _k = 0, int _x = 0, int _y = 0, int _id = 0)
      : x(_x), y(_y), k(_k), l(_l), r(_r), id(_id) {}
} sm[N], bg[N];
struct RMQ {
  int st[N][20];
  int len;
  void init() {
    for (int j = 1; j <= 17; j++)
      for (int i = len - (1 << j) + 1; i >= 0; i--)
        st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  }
  int query(int l, int r) {
    if (l > r) return inf;
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
  }
} a, b, c;
void gaosa() {
  for (int i = 1; i <= len; i++) sum[s[i]]++;
  for (int i = 1; i <= 255; i++) sum[i] += sum[i - 1];
  for (int i = len; i; i--) sa[sum[s[i]]--] = i;
  int m = 1;
  rk[sa[1]] = 1;
  for (int i = 2; i <= len; i++) {
    if (s[sa[i]] != s[sa[i - 1]]) m++;
    rk[sa[i]] = m;
  }
  for (int j = 1; m < len; j *= 2) {
    for (int i = 1; i <= m; i++) sum[i] = 0;
    memcpy(trk, rk, sizeof(rk));
    int p = 0;
    for (int i = len - j + 1; i <= len; i++) tsa[++p] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > j) tsa[++p] = sa[i] - j;
    for (int i = 1; i <= len; i++) sum[trk[tsa[i]]]++;
    for (int i = 1; i <= m; i++) sum[i] += sum[i - 1];
    for (int i = len; i; i--) sa[sum[trk[tsa[i]]]--] = tsa[i];
    m = 1;
    rk[sa[1]] = 1;
    for (int i = 2; i <= len; i++) {
      if (trk[sa[i]] != trk[sa[i - 1]] || trk[sa[i] + j] != trk[sa[i - 1] + j])
        m++;
      rk[sa[i]] = m;
    }
  }
}
void gaoh() {
  int p = 0;
  h[1] = 0;
  for (int i = 1; i <= len; i++) {
    if (rk[i] == 1) continue;
    int j = sa[rk[i] - 1];
    while (s[i + p] == s[j + p]) p++;
    h[rk[i]] = p;
    if (p) p--;
  }
  a.len = len;
  for (int i = 1; i <= len; i++) a.st[i][0] = h[i];
  a.init();
}
int lcp(int x, int y) {
  x = rk[x];
  y = rk[y];
  if (x > y) swap(x, y);
  return a.query(x + 1, y);
}
int cmp(int i, int j) {
  int flag = 0;
  if (i == j) return 0;
  if (i > j) swap(i, j), flag = 1;
  if (j - i >= m) {
    int d = (j - i) - m, w = j - i;
    int lcp1 = lcp(n + 1, i + 1);
    if (lcp1 < m) return (rk[n + 1] < rk[i + 1]) ^ flag;
    int lcp2 = lcp(i + 1, i + m + 1);
    if (lcp2 < d) return (rk[i + 1] < rk[i + m + 1]) ^ flag;
    int lcp3 = lcp(i + d + 1, n + 1);
    if (lcp3 < m) return (rk[i + d + 1] < rk[n + 1]) ^ flag;
  } else {
    int d = m - (j - i), w = j - i;
    int lcp1 = lcp(n + 1, i + 1);
    if (lcp1 < w) return (rk[n + 1] < rk[i + 1]) ^ flag;
    int lcp2 = lcp(n + w + 1, n + 1);
    if (lcp2 < d) return (rk[n + w + 1] < rk[n + 1]) ^ flag;
    int lcp3 = lcp(i + 1, n + d + 1);
    if (lcp3 < w) return (rk[i + 1] < rk[n + d + 1]) ^ flag;
  }
  return !flag;
}
int main() {
  for (int i = 2; i < N; i++) lg[i] = lg[i / 2] + 1;
  scanf("%s", t + 1);
  n = strlen(t + 1);
  for (int i = 1; i <= n; i++) s[++len] = t[i];
  scanf("%s", t + 1);
  m = strlen(t + 1);
  for (int i = 1; i <= m; i++) s[++len] = t[i];
  gaosa();
  gaoh();
  for (int i = 1; i <= n; i++) ord[i] = i;
  sort(ord, ord + n + 1, cmp);
  for (int i = 0; i <= n; i++) val[ord[i]] = i;
  for (int i = 0; i <= n; i++) b.st[i][0] = val[i];
  b.len = n;
  b.init();
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    if (k > kuai)
      bg[++cb] = node(l, r, k, x, y, i);
    else
      sm[++cm] = node(l, r, k, x, y, i);
  }
  memset(ans, -1, sizeof(ans));
  for (int i = 1; i <= cb; i++) {
    ans[bg[i].id] = inf;
    x = bg[i].x;
    y = bg[i].y;
    l = bg[i].l;
    r = bg[i].r;
    k = bg[i].k;
    for (int j = 0; j * k <= r; j++)
      ans[bg[i].id] =
          min(ans[bg[i].id], b.query(max(l, j * k + x), min(r, j * k + y)));
  }
  for (int i = 1; i <= cm; i++)
    if (ans[sm[i].id] < 0) {
      int cnt = 0;
      k = sm[i].k;
      for (int j = 0; j < k; j++)
        for (int kk = 0; kk * k + j <= n; kk++)
          c.st[cnt][0] = val[kk * k + j], id[kk * k + j] = cnt++;
      c.len = cnt;
      c.init();
      for (int j = i; j <= cm; j++)
        if (sm[j].k == sm[i].k) {
          ans[sm[j].id] = inf;
          x = sm[j].x;
          y = sm[j].y;
          l = sm[j].l;
          r = sm[j].r;
          for (int kk = x; kk <= y; kk++) {
            int L = l / k * k + kk;
            int R = r / k * k + kk;
            while (L < l) L += k;
            while (R > r) R -= k;
            if (L <= R)
              ans[sm[j].id] = min(ans[sm[j].id], c.query(id[L], id[R]));
          }
        }
    }
  for (int i = 1; i <= q; i++)
    if (ans[i] == inf)
      printf("-1 ");
    else
      printf("%d ", ord[ans[i]]);
}
