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 N = 2e5 + 5, LG = 17 + 3, SQ = 75 + 5;
int n, q, pos[N], id[N], mn[N][LG], rmq[N][LG];
int m, k, rnk[N], lg[N], rev[N], lcp[N][LG];
pair<pair<int, int>, int> x[N];
vector<int> K[SQ], P[SQ];
struct query {
  int l, r, x, y, k, ans;
  inline void check(int p) {
    if (!~ans || make_pair(id[p], p) < make_pair(id[ans], ans)) ans = p;
  }
} qu[N];
char s[N];
inline int get_lcp(int i, int j) {
  i = rnk[i], j = rnk[j];
  if (i > j) swap(i, j);
  int b = lg[j - i];
  return min(lcp[i][b], lcp[j - (1 << b)][b]);
}
inline int get_min(int i, int j) {
  int b = lg[j - i];
  return pos[min(mn[i][b], mn[j - (1 << b)][b])];
}
inline int get_rmq_min(int i, int j) {
  int b = lg[(j - i) / k];
  return pos[min(rmq[i][b], rmq[j - (1 << b) * k][b])];
}
inline int lower(int i, int x) {
  return P[i][lower_bound(P[i].begin(), P[i].end(), x) - P[i].begin()];
}
inline bool cmp(int i, int j) {
  if (i > j) return !cmp(j, i);
  int p = get_lcp(n, i);
  if (p < min(m - n, j - i)) return s[n + p] < s[i + p];
  if (m - n < j - i) {
    int p1 = get_lcp(i, i + p);
    if (p + p1 < j - i) return s[i + p1] < s[i + p + p1];
    p1 = j - i - p;
    int p2 = get_lcp(i + p1, n);
    if (p2 < m - n) return s[i + p1 + p2] < s[n + p2];
    return true;
  }
  p = j - i;
  int p1 = get_lcp(n, n + p);
  if (p + p1 < m - n) return s[n + p + p1] < s[n + p1];
  int p2 = get_lcp(i, n + p1);
  if (p1 + p2 < m - n) return s[i + p2] < s[n + p1 + p2];
  return true;
}
inline void set_rank() {
  sort(x, x + m);
  for (int i = 1, cur = 0; i < m; i++)
    rnk[x[i].second] = cur += x[i].first != x[i - 1].first;
}
inline void make_suffix_array() {
  for (int i = 0; i < m; i++) x[i] = {{s[i], 0}, i};
  set_rank();
  for (int i = 0; m >> i; i++) {
    for (int j = 0; j < m; j++)
      x[j] = {{rnk[j], j + (1 << i) < m ? rnk[j + (1 << i)] : -1}, j};
    set_rank();
  }
}
inline void make_lcp_array() {
  rev[m] = m;
  for (int i = 0; i < m; i++) rev[rnk[i]] = i;
  for (int i = 0, cur = 0; i < m; i++) {
    cur = max(cur, 0);
    while (s[i + cur] == s[rev[rnk[i] + 1] + cur]) cur++;
    lcp[rnk[i]][0] = cur--;
  }
  for (int i = m - 1; ~i; i--)
    for (int j = 0; j < LG - 1; j++)
      lcp[i][j + 1] =
          min(lcp[i][j], i + (1 << j) < m ? lcp[i + (1 << j)][j] : m);
  for (int i = 2; i <= m; i++) lg[i] = lg[i / 2] + 1;
}
inline void set_position_rank() {
  iota(pos, pos + n, 0);
  sort(pos, pos + n, cmp);
  for (int i = 0; i < n; i++) id[pos[i]] = mn[pos[i]][0] = i;
  for (int i = n - 1; ~i; i--)
    for (int j = 0; 1 << j < n; j++)
      mn[i][j + 1] = min(mn[i][j], i + (1 << j) < n ? mn[i + (1 << j)][j] : n);
}
inline void make_rmq() {
  for (int i = 0; i < k; i++) P[i].clear();
  for (int i = 0; i < n + k; i++) P[i % k].push_back(i);
  for (int i = n - 1; ~i; i--) {
    rmq[i][0] = id[i];
    for (int j = 0; (1 << j) * k < n; j++)
      rmq[i][j + 1] =
          min(rmq[i][j], i + (1 << j) * k < n ? rmq[i + (1 << j) * k][j] : n);
  }
}
inline void answer_queries() {
  for (k = 1; k < SQ; k++) {
    if (K[k].empty()) continue;
    make_rmq();
    for (auto p : K[k])
      for (int i = qu[p].x; i < qu[p].x + qu[p].y; i++)
        if (lower(i, qu[p].l) ^ lower(i, qu[p].r))
          qu[p].check(get_rmq_min(lower(i, qu[p].l), lower(i, qu[p].r)));
  }
  for (int i = 0; i < q; i++) {
    if (~qu[i].ans) continue;
    for (int j = qu[i].l / qu[i].k * qu[i].k + qu[i].x; j < qu[i].r;
         j += qu[i].k) {
      int st = max(j, qu[i].l), en = min(j + qu[i].y, qu[i].r);
      if (st < en) qu[i].check(get_min(st, en));
    }
  }
}
inline void read_input() {
  scanf("%s", s);
  n = strlen(s) + 1;
  scanf("%s%d", s + n, &q);
  m = n + strlen(s + n);
  for (int i = 0; i < q; i++) {
    int l, r, x, y, k;
    scanf("%d%d%d%d%d", &l, &r, &k, &x, &y);
    qu[i] = {l, ++r, x, ++y - x, k, -1};
    if (k < SQ) K[k].push_back(i);
  }
}
inline void solve() {
  make_suffix_array();
  make_lcp_array();
  set_position_rank();
  answer_queries();
}
inline void write_output() {
  for (int i = 0; i < q; i++) printf("%d ", qu[i].ans);
}
int main() {
  read_input();
  solve();
  write_output();
}
