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>
#pragma GCC target("arch=corei7-avx")
const int N = 2e5 + 5, inf = 1e9 + 7;
using namespace std;
char s[N], t[N];
int p[N], Rank[N], LOG[N], len;
vector<int> f[101][20];
int m, n, Mid, bin[N], rk[N], sa[N], tmp[N], height[N], G[N][21], R[N][21],
    cnt[101], val[101][N];
struct epoch {
  int l, r, k, x, y, id, ans;
} a[N];
void SuffixArray() {
  int sz = max(300, n);
  for (int i = 0; i <= sz - 1; ++i) bin[i] = 0;
  for (int i = 0; i <= n - 1; ++i) rk[i] = s[i];
  for (int i = 0; i <= n - 1; ++i) ++bin[rk[i]];
  for (int i = 1; i <= sz - 1; ++i) bin[i] += bin[i - 1];
  for (int i = n - 1; i >= 0; --i) sa[--bin[rk[i]]] = i;
  for (int j = 1; j <= n; j <<= 1) {
    int p = 0;
    for (int i = n - j; i <= n - 1; ++i) tmp[p++] = i;
    for (int i = 0; i <= n - 1; ++i)
      if (sa[i] - j >= 0) tmp[p++] = sa[i] - j;
    for (int i = 0; i <= sz - 1; ++i) bin[i] = 0;
    for (int i = 0; i <= n - 1; ++i) ++bin[rk[i]];
    for (int i = 1; i <= sz - 1; ++i) bin[i] += bin[i - 1];
    for (int i = n - 1; i >= 0; --i) sa[--bin[rk[tmp[i]]]] = tmp[i];
    p = 0, tmp[sa[0]] = 0;
    for (int i = 1; i <= n - 1; ++i) {
      int v0 = sa[i - 1], v1 = sa[i], v00, v01;
      if (v0 + j < n)
        v00 = rk[v0 + j];
      else
        v00 = -1;
      if (v1 + j < n)
        v01 = rk[v1 + j];
      else
        v01 = -1;
      if (rk[v0] == rk[v1] && v00 == v01)
        tmp[sa[i]] = p;
      else
        tmp[sa[i]] = ++p;
    }
    for (int i = 0; i <= n - 1; ++i) rk[i] = tmp[i];
  }
}
int Calc(int i, int j, int ret) {
  for (; i + ret < n && j + ret < n && s[i + ret] == s[j + ret];) ++ret;
  return ret;
}
void CalcHeight() {
  if (rk[0] == 0)
    height[0] = 0;
  else
    height[0] = Calc(0, sa[rk[0] - 1], 0);
  for (int i = 1; i <= n - 1; ++i)
    if (rk[i] == 0)
      height[i] = 0;
    else
      height[i] = Calc(i, sa[rk[i] - 1], max(height[i - 1] - 1, 0));
  for (int i = 1; i <= n - 1; ++i) {
    G[i][0] = height[sa[i]];
  }
  for (int j = 1; j <= 20; ++j)
    for (int i = 1; i <= n - (1 << (j - 1)); ++i) {
      G[i][j] = min(G[i][j - 1], G[i + (1 << (j - 1))][j - 1]);
    }
  for (int i = 1; i <= n; ++i) LOG[i] = floor(log(i) / log(2) + (1e-17));
}
inline int CntLcp(int l, int r) {
  l = rk[l], r = rk[r];
  if (l > r) swap(l, r);
  if (l == r) return inf;
  ++l;
  int i = LOG[r - l + 1];
  return min(G[l][i], G[r - (1 << i) + 1][i]);
}
inline bool Cmp(int x, int y) {
  int l, X = max(x, y), Y = min(x, y);
  int pos1, pos2;
  if (X - Y >= len) {
    pos1 = Mid + 1, pos2 = Y;
    l = CntLcp(pos1, pos2);
    if (l < len) {
      pos1 += l, pos2 += l;
      if (x < y) {
        return s[pos1] < s[pos2];
      } else {
        return s[pos2] < s[pos1];
      }
    }
    pos1 = Y, pos2 = Y + len;
    l = CntLcp(pos1, pos2);
    if (l < X - Y - len) {
      pos1 += l, pos2 += l;
      if (x < y) {
        return s[pos1] < s[pos2];
      } else {
        return s[pos2] < s[pos1];
      }
    }
    pos1 = X - len, pos2 = Mid + 1;
    l = CntLcp(pos1, pos2);
    if (l < len) {
      pos1 += l, pos2 += l;
      if (x < y) {
        return s[pos1] < s[pos2];
      } else {
        return s[pos2] < s[pos1];
      }
    }
    return x < y;
  }
  pos1 = Mid + 1, pos2 = Y;
  l = CntLcp(pos1, pos2);
  if (l < X - Y) {
    pos1 += l, pos2 += l;
    if (x < y) {
      return s[pos1] < s[pos2];
    } else {
      return s[pos2] < s[pos1];
    }
  }
  pos1 = Mid + 1 + X - Y, pos2 = Mid + 1;
  l = CntLcp(pos1, pos2);
  if (l < len - X + Y) {
    pos1 += l, pos2 += l;
    if (x < y) {
      return s[pos1] < s[pos2];
    } else {
      return s[pos2] < s[pos1];
    }
  }
  pos1 = Y, pos2 = Mid + 1 + len - X + Y;
  l = CntLcp(pos1, pos2);
  if (l < X - Y) {
    pos1 += l, pos2 += l;
    if (x < y) {
      return s[pos1] < s[pos2];
    } else {
      return s[pos2] < s[pos1];
    }
  }
  return x < y;
}
void Pre() {
  n = strlen(s);
  s[n] = '#';
  for (int i = n + 1; i <= n + len; ++i) {
    s[i] = t[i - n - 1];
  }
  Mid = n;
  n += len + 1;
  SuffixArray();
  CalcHeight();
  n = Mid;
  for (int i = 0; i <= n; ++i) {
    p[i] = i;
  }
  sort(p, p + n + 1, Cmp);
  for (int i = 0; i <= n; ++i) {
  }
  for (int i = 0; i <= n; ++i) {
    Rank[p[i]] = i;
  }
  for (int i = 0; i <= n; ++i) {
    R[i][0] = Rank[i];
  }
  for (int j = 1; j <= 20; ++j)
    for (int i = 0; i <= n - (1 << (j - 1)) + 1; ++i) {
      R[i][j] = min(R[i][j - 1], R[i + (1 << (j - 1))][j - 1]);
    }
}
bool Cmpk(epoch a, epoch b) { return a.k < b.k; }
void Build(int k) {
  for (int i = 0; i <= k - 1; ++i)
    for (int j = 0; j <= 19; ++j) f[i][j].clear();
  for (int i = 0; i <= k - 1; ++i) {
    cnt[i] = 0;
    for (int j = i; j <= n; j += k) {
      val[i][++cnt[i]] = j;
    }
    for (int j = 0; j <= cnt[i]; ++j)
      for (int c = 0; c <= 19; ++c) f[i][c].push_back(0);
    for (int j = i, v = 1; j <= n; j += k, ++v) {
      f[i][0][v] = Rank[j];
    }
    for (int c = 1; c <= LOG[cnt[i]]; ++c)
      for (int j = 1; j <= cnt[i] - (1 << (c - 1)) + 1; ++j) {
        f[i][c][j] = min(f[i][c - 1][j], f[i][c - 1][j + (1 << (c - 1))]);
      }
  }
}
int find(int c, int x) {
  int l = 1, r = cnt[c], res = r + 1;
  for (; l <= r;) {
    int mid = (l + r) / 2;
    if (val[c][mid] >= x) {
      res = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return res;
}
inline int GetMn(int c, int l, int r) {
  if (l > r) return inf;
  int i = LOG[r - l + 1];
  return min(f[c][i][l], f[c][i][r - (1 << i) + 1]);
}
inline int GetR(int l, int r) {
  if (l > r) return inf;
  int i = LOG[r - l + 1];
  return min(R[l][i], R[r - (1 << i) + 1][i]);
}
void Query(epoch &u) {
  u.ans = inf;
  for (int i = u.x; i <= u.y; ++i) {
    u.ans = min(u.ans, GetMn(i, find(i, u.l), find(i, u.r + 1) - 1));
  }
}
void Calc(epoch &u) {
  u.ans = inf;
  for (int l = u.x, r = u.y; l <= n; l += u.k, r += u.k) {
    u.ans = min(u.ans, GetR(max(l, u.l), min(r, u.r)));
  }
}
bool CmpID(epoch a, epoch b) { return a.id < b.id; }
void Solve() {
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d%d%d", &a[i].l, &a[i].r, &a[i].k, &a[i].x, &a[i].y);
    a[i].id = i;
  }
  int lim = min(n, 50);
  sort(a + 1, a + m + 1, Cmpk);
  int i, j;
  for (i = 1; i <= m; i = j) {
    if (a[i].k <= lim) {
      for (j = i + 1; j <= m && a[i].k == a[j].k; ++j)
        ;
      Build(a[i].k);
      for (int k = i; k <= j - 1; ++k) {
        Query(a[k]);
      }
    } else {
      Calc(a[i]);
      j = i + 1;
    }
  }
  sort(a + 1, a + m + 1, CmpID);
  for (int i = 1; i <= m; ++i) {
    if (a[i].ans == inf) {
      printf("-1 ");
    } else {
      printf("%d ", p[a[i].ans]);
    }
  }
  puts("");
}
int main() {
  scanf("%s%s%d", s, t, &m);
  len = strlen(t);
  Pre();
  Solve();
  return 0;
}
