#include <bits/stdc++.h>   using namespace std;   const int MAXS = 200005;   const int MAXN = 100005;   const int B = 75;   template <typename T>   inline void read(T &AKNOI) {     T x = 0, flag = 1;     char ch = getchar();     while (!isdigit(ch)) {       if (ch ==  - ) flag = -1;       ch = getchar();     }     while (isdigit(ch)) {       x = x * 10 + ch -  0 ;       ch = getchar();     }     AKNOI = flag * x;   }   template <typename T>   inline void cmin(T &x, T y) {     if (x > y) x = y;   }   template <typename T>   inline void cmax(T &x, T y) {     if (x < y) x = y;   }   char ss[MAXS], tt[MAXS];   int lg2[MAXS];   struct SuffixArray {     int sa[MAXS], x[MAXS], y[MAXS], cnt[MAXS];     int rnk[MAXS], hei[MAXS], st[MAXS][20];     inline bool cmp(int i, int j, int k) {       return (y[i] == y[j] && y[i + k] == y[j + k]);     }     void build(int n) {       int m = 256;       for (int i = 1; i <= n; ++i) {         ++cnt[x[i] = ss[i]];       }       for (int i = 1; i <= m; ++i) {         cnt[i] += cnt[i - 1];       }       for (int i = n; i >= 1; --i) {         sa[cnt[x[i]]--] = i;       }       for (int k = 1; k <= n; k <<= 1) {         int p = 0;         for (int i = n - k + 1; i <= n; ++i) {           y[++p] = i;         }         for (int i = 1; i <= n; ++i) {           if (sa[i] > k) {             y[++p] = sa[i] - k;           }         }         for (int i = 0; i <= m; ++i) {           cnt[i] = 0;         }         for (int i = 1; i <= n; ++i) {           ++cnt[x[y[i]]];         }         for (int i = 1; i <= m; ++i) {           cnt[i] += cnt[i - 1];         }         for (int i = n; i >= 1; --i) {           sa[cnt[x[y[i]]]--] = y[i];         }         swap(x, y);         x[sa[1]] = p = 1;         for (int i = 2; i <= n; ++i) {           x[sa[i]] = (cmp(sa[i], sa[i - 1], k) ? p : ++p);         }         if (p >= n) break;         m = p;       }       for (int i = 1; i <= n; ++i) {         rnk[sa[i]] = i;       }       for (int i = 1, j = 0; i <= n; ++i) {         if (j) --j;         while (ss[i + j] == ss[sa[rnk[i] - 1] + j]) ++j;         hei[rnk[i]] = j;       }       lg2[1] = 0;       for (int i = 2; i <= n; ++i) {         lg2[i] = lg2[i >> 1] + 1;       }       for (int i = n; i >= 1; --i) {         st[i][0] = hei[i];         for (int j = 1; i + (1 << j) - 1 <= n; ++j) {           st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);         }       }     }     inline int LCP(int x, int y) {       if (x == y) return MAXS;       int l = rnk[x], r = rnk[y];       if (l > r) swap(l, r);       int k = lg2[r - l];       return min(st[l + 1][k], st[r - (1 << k) + 1][k]);     }     inline int sgn(int x, int y, int len) {       if (LCP(x, y) >= len) return 0;       return (rnk[x] < rnk[y]) ? -1 : 1;     }   } SA;   int n, m, Q, sor[MAXN], rnk[MAXN], ans[MAXN];   inline bool cmp(int x, int y) {     static int t;     bool swp = (x > y);     if (swp) swap(x, y);     if (x + m <= y) {       t = SA.sgn(n + 2, x + 1, m);       if (t) return (t < 0) ^ swp;       t = SA.sgn(x + 1, x + m + 1, y - x - m);       if (t) return (t < 0) ^ swp;       t = SA.sgn(y - m + 1, n + 2, m);       if (t) return (t < 0) ^ swp;     } else {       t = SA.sgn(n + 2, x + 1, y - x);       if (t) return (t < 0) ^ swp;       t = SA.sgn(n + 2 + y - x, n + 2, x + m - y);       if (t) return (t < 0) ^ swp;       t = SA.sgn(x + 1, n + 2 + x + m - y, y - x);       if (t) return (t < 0) ^ swp;     }     return swp ^ 1;   }   struct Query {     int l, r, x, y, id;   } tmp;   vector<Query> q[80];   struct SparseTable {     int st[MAXN][20];     void build(int n) {       for (int i = n; i >= 0; --i) {         for (int j = 1; i + (1 << j) - 1 <= n; ++j) {           st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);         }       }     }     int query(int l, int r) {       int k = lg2[r - l + 1];       return min(st[l][k], st[r - (1 << k) + 1][k]);     }   } ST;   void Work1(Query p, int k) {     for (int x = p.x, y = p.y; x <= n; x += k, y += k) {       int l = max(p.l, x), r = min(p.r, y);       if (l > r) continue;       cmin(ans[p.id], ST.query(l, r));     }   }   void Work2(int k) {     for (int x = 0; x < k; ++x) {       int cnt = 0;       for (int i = x; i <= n; i += k) {         ST.st[cnt++][0] = rnk[i];       }       ST.build(cnt - 1);       for (auto p : q[k]) {         if (x < p.x || x > p.y) continue;         int l = p.l / k + (p.l % k > x);         int r = p.r / k - (p.r % k < x);         if (l > r) continue;         cmin(ans[p.id], ST.query(l, r));       }     }   }   void init() {     scanf( %s , ss + 1);     n = strlen(ss + 1);     scanf( %s , tt + 1);     m = strlen(tt + 1);     ss[n + 1] =  # ;     for (int i = 1; i <= m; ++i) {       ss[n + 1 + i] = tt[i];     }     SA.build(n + 1 + m);     for (int i = 0; i <= n; ++i) {       sor[i] = i;     }     sort(sor, sor + n + 1, cmp);     for (int i = 0; i <= n; ++i) {       rnk[sor[i]] = i;     }   }   void solve() {     for (int i = 0; i <= n; ++i) {       ST.st[i][0] = rnk[i];     }     ST.build(n);     read(Q);     memset(ans, 0x3f, sizeof(ans));     for (int i = 1, k; i <= Q; ++i) {       read(tmp.l);       read(tmp.r);       read(k);       read(tmp.x);       read(tmp.y);       tmp.id = i;       if (k > B) {         Work1(tmp, k);       } else {         q[k].push_back(tmp);       }     }     for (int i = 1; i <= B; ++i) {       Work2(i);     }     for (int i = 1; i <= Q; ++i) {       printf( %d  , (ans[i] <= n) ? sor[ans[i]] : -1);     }   }   int main() {     init();     solve();     return 0;   }   