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>
template <typename T, typename U, typename Cmp>
struct byFieldComparer {
  U T::*p;
  Cmp cmp;
  byFieldComparer(U T::*p, Cmp cmp) : p(p), cmp(cmp) {}
  bool operator()(const T& a, const T& b) const { return cmp(a.*p, b.*p); }
};
template <typename T, typename U, typename Cmp>
byFieldComparer<T, U, Cmp> byField(U T::*p, Cmp cmp) {
  return {p, cmp};
}
template <typename T, typename U>
byFieldComparer<T, U, std::less<U>> byField(U T::*p) {
  return {p, {}};
}
template <typename T>
void minup(T& x, T&& y) {
  if (y < x) x = y;
}
template <typename T>
void minup(T& x, const T& y) {
  if (y < x) x = y;
}
template <typename T>
void maxup(T& x, T&& y) {
  if (y > x) x = y;
}
template <typename T>
void maxup(T& x, const T& y) {
  if (y > x) x = y;
}
static constexpr unsigned bhash_primes[]{2672090437};
struct bhash {
  static constexpr int np = sizeof(bhash_primes) / sizeof(*bhash_primes);
  static std::array<unsigned, np> const& pow2(size_t n) {
    static std::vector<std::array<unsigned, np>> pow2_mem{[] {
      std::array<unsigned, np> a;
      for (auto& x : a) x = 1;
      return a;
    }()};
    size_t i = pow2_mem.size();
    if (i <= n) {
      for (; i <= n; i++) {
        pow2_mem.emplace_back();
        for (int j = 0; j < np; j++)
          pow2_mem[i][j] = pow2_mem[i - 1][j] * uint64_t(2) % bhash_primes[j];
      }
    }
    return pow2_mem[n];
  }
  unsigned m[np];
  int nbits;
  bhash() {}
  bhash(unsigned num, int nbits) : nbits(nbits) {
    for (int i = 0; i < np; i++) m[i] = num;
  }
  bhash operator+(const bhash& b) const {
    bhash out;
    out.nbits = nbits + b.nbits;
    auto& p2 = pow2(b.nbits);
    for (int i = 0; i < np; i++)
      out.m[i] = (m[i] * (uint64_t)p2[i] + b.m[i]) % bhash_primes[i];
    return out;
  }
  bhash removePrefix(const bhash& prefix) const {
    bhash out;
    out.nbits = nbits - prefix.nbits;
    auto& p2 = pow2(out.nbits);
    for (int i = 0; i < np; i++)
      out.m[i] = (m[i] + prefix.m[i] * uint64_t(bhash_primes[i] - p2[i])) %
                 bhash_primes[i];
    return out;
  }
};
bool operator<(const bhash& a, const bhash& b) {
  if (a.nbits != b.nbits) return a.nbits < b.nbits;
  for (int i = 0; i < bhash::np; i++) {
    if (a.m[i] != b.m[i]) return a.m[i] < b.m[i];
  }
  return false;
}
namespace intrinsics {
template <int>
struct integer;
template <typename, typename = void>
struct impl;
template <typename _>
struct impl<integer<4>, _> {
  static int BSR(unsigned x) { return __builtin_clz(x) ^ 31; }
};
template <typename _>
struct impl<integer<1>, _> {
  template <typename T>
  static int BSR_ms(T x) {
    unsigned long result;
    _BitScanReverse(&result, x);
    return result;
  }
  static int BSR(unsigned x) { return BSR_ms(x); }
};
static int BSR(unsigned x) {
  char(4);
  (void)4;
  return impl<integer<sizeof(4)>>::BSR(x);
}
};  // namespace intrinsics
template <typename T, typename Op>
struct sparse_table {
  std::unique_ptr<T[]> dat;
  int size;
  sparse_table() {}
  sparse_table(int size) : size(size) {
    if (size) {
      int bl = intrinsics::BSR(size) + 1;
      dat.reset(new T[bl * size - (1 << bl) + bl + 1]);
    }
  }
  T* data() { return dat.get(); }
  void calc() {
    T* p2 = dat.get();
    T* out = p2 + size;
    for (int sz = 1;;) {
      T* p1 = p2;
      p2 += sz;
      sz <<= 1;
      if (sz > size) break;
      for (int i = size - sz + 1; i--;) *out++ = Op()(*p1++, *p2++);
    }
  }
  T operator()(int a, int b) const {
    assert(a >= 0 && b <= size && b >= a);
    int d = b - a;
    if (!d) return T();
    int logd = intrinsics::BSR(d);
    T* off = dat.get() + (logd * size - (1 << logd) + logd + 1);
    return Op()(off[a], off[b - (1 << logd)]);
  }
  const T& operator[](int a) const {
    assert(a >= 0 && a < size);
    return dat[a];
  }
};
using std::string;
using std::vector;
vector<bhash> prefixes(const string& s) {
  vector<bhash> p(s.size() + 1);
  p[0] = {0, 0};
  for (int i = 0; i < (int)s.size(); i++) p[i + 1] = p[i] + bhash(s[i] & 31, 5);
  return p;
}
vector<int> sortedPositions(const string& S, const string& T) {
  auto Spre = prefixes(S);
  auto Tpre = prefixes(T);
  auto h = [&](int i, int len) {
    bhash h;
    if (len <= i)
      h = Spre[len];
    else if (len <= i + (int)T.size())
      h = Spre[i] + Tpre[len - i];
    else
      h = Spre[i] + Tpre.back() + Spre[len - T.size()].removePrefix(Spre[i]);
    return h;
  };
  auto nthChar = [&](int i, int n) {
    if (n < i) return S[n];
    if (n < i + (int)T.size()) return T[n - i];
    return S[n - T.size()];
  };
  auto lt = [&](int i, int j) {
    unsigned lo = 0, hi = unsigned(T.size() + S.size());
    while (hi > lo) {
      unsigned mid = (hi + lo + 1) / 2;
      auto ih = h(i, mid), jh = h(j, mid);
      for (int i = 0; i < bhash::np; i++) {
        if (ih.m[i] != jh.m[i]) {
          hi = mid - 1;
          goto nx;
        }
      }
      { lo = mid; }
    nx:;
    }
    bool ans;
    if (lo == S.size() + T.size())
      ans = i < j;
    else
      ans = nthChar(i, lo) < nthChar(j, lo);
    assert(S.size() + T.size() > 500 || ans == [&] {
      int cmp = (S.substr(0, i) + T + S.substr(i))
                    .compare(S.substr(0, j) + T + S.substr(j));
      return cmp ? cmp < 0 : i < j;
    }());
    return ans;
  };
  vector<int> inds(S.size() + 1);
  for (int i = (int)S.size(); i >= 0; i--) inds[i] = i;
  std::stable_sort(inds.begin(), inds.end(), lt);
  return inds;
}
struct query {
  int l, r, k, x, y;
  int id;
};
vector<int> solve(const string& S, const string& T, std::vector<query> Q) {
  auto inds = sortedPositions(S, T);
  vector<int> p(inds.size());
  for (auto i = inds.size(); i--;) p[inds[i]] = (int)i;
  inds.push_back(-1);
  struct min_s {
    int operator()(int a, int b) { return std::min(a, b); }
  };
  using ST = sparse_table<int, min_s>;
  auto makeST = [&p](int mod, int res) {
    ST st(((int)p.size() - res + mod - 1) / mod);
    int* z = st.data();
    for (int i = res; i < (int)p.size(); i += mod) *z++ = p[i];
    assert(z - st.data() == st.size);
    st.calc();
    return st;
  };
  std::sort(Q.begin(), Q.end(), byField(&query::k));
  vector<int> out(Q.size());
  auto it = Q.begin();
  for (int k = 1; k * k < S.size(); k++) {
    vector<ST> t(k);
    for (int m = 0; m < k; m++) t[m] = makeST(k, m);
    for (; it != Q.end() && it->k == k; ++it) {
      int min = (int)p.size();
      for (int m = it->x; m <= it->y; m++) {
        int a = (it->l - m + k - 1) / k;
        int b = (it->r - m + k) / k;
        if (b > a) minup(min, t[m](a, b));
      }
      out[it->id] = inds[min];
    }
  }
  auto st = makeST(1, 0);
  for (; it != Q.end(); ++it) {
    int min = (int)p.size();
    for (int x = it->x - it->k; x <= (int)S.size(); x += it->k) {
      int a = std::max(x, it->l);
      int b = std::min(x + (it->y - it->x + 1), it->r + 1);
      if (b > a) minup(min, st(a, b));
    }
    out[it->id] = inds[min];
  }
  return out;
}
vector<int> solve2(const string& S, const string& T, std::vector<query> Q) {
  auto nthChar = [&](int i, int n) {
    if (n < i) return S[n];
    if (n < i + (int)T.size()) return T[n - i];
    return S[n - T.size()];
  };
  vector<int> out;
  for (query q : Q) {
    int a = -1;
    for (int i = q.l; i <= q.r; i++) {
      if (!(i % q.k >= q.x && i % q.k <= q.y)) continue;
      if (a == -1) {
        a = i;
        continue;
      }
      for (int j = 0; j < int(S.size() + T.size()); j++) {
        char ci = nthChar(i, j);
        char ca = nthChar(a, j);
        if (ci < ca) {
          a = i;
          break;
        } else if (ci > ca) {
          break;
        }
      }
    }
    out.push_back(a);
  }
  return out;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  string S, T;
  int q;
  std::cin >> S >> T >> q;
  vector<query> Q(q);
  for (int i = 0; i < q; i++) {
    auto& z = Q[i];
    std::cin >> z.l >> z.r >> z.k >> z.x >> z.y;
    z.id = i;
  }
  auto out = solve(S, T, Q);
  assert(solve2(S, T, Q) == out);
  for (int a : out) std::cout << a << ' ';
  return 0;
}
