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 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;
}
