#include <bits/stdc++.h>
#pragma optimize("Ofast")
const int maxn = 2E+5 + 5;
int n, m, lg[maxn];
char str[maxn], *S, *T;
namespace Sub1 {
int ST[18][maxn];
namespace SA {
int n, m, x[maxn], y[maxn], c[maxn];
int hei[maxn], rk[maxn], sa[maxn];
inline void SA() {
  m = 122, n = ::n + ::m;
  for (int i = 1; i <= n; ++i) x[i] = str[i], ++c[x[i]];
  for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i >= 1; --i) sa[c[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int num = 0;
    for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > k) y[++num] = sa[i] - k;
    for (int i = 1; i <= m; ++i) c[i] = 0;
    for (int i = 1; i <= n; ++i) ++c[x[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i >= 1; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
    std::swap(x, y);
    num = 1, x[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
        x[sa[i]] = num;
      else
        x[sa[i]] = ++num;
    }
    if (num == n) break;
    m = num;
  }
  int k = 0;
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (rk[i] == 1) continue;
    if (k) --k;
    int j = sa[rk[i] - 1];
    while (i + k <= n && j + k <= n && str[i + k] == str[j + k]) ++k;
    hei[rk[i]] = k;
  }
}
inline void getST() {
  for (int i = 1; i <= n; ++i) ST[0][i] = hei[i];
  int Len = log2(n);
  for (int len = 1; len <= Len; ++len)
    for (int i = 1; i <= n; ++i) {
      ST[len][i] = ST[len - 1][i];
      if (i + (1 << len - 1) <= n)
        ST[len][i] = std::min(ST[len][i], ST[len - 1][i + (1 << len - 1)]);
    }
  lg[0] = -1;
  for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
}
}  // namespace SA
inline int lcp(int x, int y) {
  x = SA::rk[x], y = SA::rk[y];
  if (x > y) std::swap(x, y);
  ++x;
  int len = log2(y - x + 1);
  int res = std::min(ST[len][x], ST[len][y - (1 << len) + 1]);
  return res;
}
inline bool cmp(int i, int j) {
  if (i == j) return 1;
  bool f = 0;
  if (i > j) std::swap(i, j), f = 1;
  int p = j - i, k = std::min(p, m), l = lcp(n + 1, i + 1);
  if (l < k) return f ^ (T[l + 1] < S[i + l + 1]);
  if (p < m) {
    int t = m - p;
    l = lcp(n + m - t + 1, n + 1);
    if (l < t) return f ^ (T[m - t + 1 + l] < T[l + 1]);
  }
  if (p > m) {
    int t = p - m;
    l = lcp(i + 1, j - t + 1);
    if (l < t) return f ^ (S[i + l + 1] < S[j - t + 1 + l]);
  }
  l = lcp(j - k + 1, n + m - k + 1);
  if (l < k) return f ^ (S[j - k + 1 + l] < T[m - k + 1 + l]);
  return !f;
}
}  // namespace Sub1
inline int getint(int x = 0) {
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x;
}
int s[32], t;
inline void putint(int x = 0, char suf = ' ') {
  if (!x) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  while (x) s[++t] = x % 10, x /= 10;
  while (t) putchar(s[t--] + '0');
  putchar(suf);
}
namespace Sub2 {
const int B = 88;
int q, p[maxn], pp[maxn], cnt, ans[maxn];
struct Query {
  int l, r, k, x, y, id;
} qry[maxn];
int h[maxn];
std::vector<int> st[B][17];
inline void getST(std::vector<int> *st, int n) {
  st[0].resize(n + 1), st[0].shrink_to_fit();
  for (int i = 0; i <= n; ++i) st[0][i] = h[i];
  int Len = lg[n + 1];
  for (int len = 1; len <= Len; ++len) {
    st[len].resize(n + 1), st[len].shrink_to_fit();
    for (int i = 0; i <= n; ++i) {
      st[len][i] = st[len - 1][i];
      if (i + (1 << len - 1) <= n)
        st[len][i] = std::min(st[len][i], st[len - 1][i + (1 << len - 1)]);
    }
  }
}
inline int ST(std::vector<int> *st, int l, int r) {
  int len = lg[r - l + 1];
  return std::min(st[len][l], st[len][r - (1 << len) + 1]);
}
void main() {
  for (int i = 0; i <= n; ++i) p[i] = i;
  std::sort(p, p + n + 1, Sub1::cmp);
  for (int i = 0; i <= n; ++i) h[p[i]] = pp[p[i]] = i;
  getST(st[0], n), q = getint();
  for (int i = 1; i <= q; ++i) {
    int l = getint(), r = getint(), k = getint(), x = getint(), y = getint();
    ans[i] = 1E+9;
    if ((r - l + 1) / k <= n / B) {
      for (int t = 0; t * k <= n; ++t) {
        int L = t * k + x, R = t * k + y;
        if (!(L <= r && R >= l)) continue;
        L = std::max(L, l), R = std::min(R, r);
        ans[i] = std::min(ans[i], ST(st[0], L, R));
      }
    } else
      qry[++cnt] = {l, r, k, x, y, i};
  }
  std::sort(qry + 1, qry + cnt + 1, [](Query x, Query y) { return x.k < y.k; });
  for (int i = 1, k = -1; i <= cnt; ++i) {
    if (qry[i].k != k) {
      k = qry[i].k;
      for (int t = 0; t < k; ++t) {
        for (int l = t; l <= n; l += k) h[l / k] = pp[l];
        getST(st[t], (n - t) / k);
      }
    }
    for (int t = qry[i].x; t <= qry[i].y; ++t) {
      int L = ceil(1.0 * (qry[i].l - t) / k);
      int R = floor(1.0 * (qry[i].r - t) / k);
      if (L <= R) ans[qry[i].id] = std::min(ans[qry[i].id], ST(st[t], L, R));
    }
  }
  for (int i = 1; i <= q; ++i) putint(ans[i] < 1E+9 ? p[ans[i]] : -1);
}
}  // namespace Sub2
int main() {
  scanf("%s", str + 1), n = strlen(str + 1), S = str;
  scanf("%s", str + n + 1), m = strlen(str + n + 1), T = str + n;
  Sub1::SA::SA(), Sub1::SA::getST(), Sub2::main();
}
