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;
template <class T, class S>
ostream& operator<<(ostream& os, const pair<T, S>& v) {
  return os << "(" << v.first << ", " << v.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (int i = int(0); i <= int((static_cast<int>((v).size())) - 1); ++i) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}
template <class T>
bool setmax(T& _a, T _b) {
  if (_b > _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
bool setmin(T& _a, T _b) {
  if (_b < _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
T gcd(T _a, T _b) {
  return _b == 0 ? _a : gcd(_b, _a % _b);
}
template <int N>
struct RMQ {
  int log[N + 1];
  int val[20][N];
  RMQ() {
    for (int k = 0; (1 << k) <= N; ++k) {
      for (int i = int(1 << k); i <= int((1 << (k + 1)) - 1); ++i) log[i] = k;
    }
  }
  void init(const int* a, int n) {
    int k = log[n];
    for (int i = int(0); i <= int((n)-1); ++i) {
      val[0][i] = a[i];
    }
    for (int j = int(0); j <= int((k)-1); ++j) {
      for (int i = int(0); i <= int((n - (1 << j)) - 1); ++i) {
        val[j + 1][i] = min(val[j][i], val[j][i + (1 << j)]);
      }
    }
  }
  void init(const vector<int>& a) { init(&a[0], static_cast<int>((a).size())); }
  int query(int l, int r) const {
    int j = log[r - l];
    return min(val[j][l], val[j][r - (1 << j)]);
  }
};
struct LCP {
  struct Node {
    const int len;
    Node *succ[26], *f;
    vector<Node*> children;
    int label;
    Node(int l, Node* copy = nullptr) : len(l) {
      if (copy) {
        memcpy(succ, copy->succ, sizeof(succ));
        f = copy->f;
      } else {
        memset(succ, 0, sizeof(succ));
        f = nullptr;
      }
    }
  } * root, *last;
  vector<Node*> nodes;
  vector<Node*> all_nodes;
  Node* extend(int ch) {
    Node *p = last, *np = new Node(p->len + 1);
    all_nodes.push_back(np);
    for (; p && !p->succ[ch]; p = p->f) {
      p->succ[ch] = np;
    }
    if (!p) {
      np->f = root;
    } else {
      Node* q = p->succ[ch];
      if (q->len == p->len + 1) {
        np->f = q;
      } else {
        Node* nq = new Node(p->len + 1, q);
        all_nodes.push_back(nq);
        q->f = np->f = nq;
        for (; p && p->succ[ch] == q; p = p->f) {
          p->succ[ch] = nq;
        }
      }
    }
    return last = np;
  }
  RMQ<800010> rmq;
  LCP(const string& s) {
    root = last = new Node(0);
    nodes.resize(static_cast<int>((s).size()));
    for (int i = int((static_cast<int>((s).size())) - 1); i >= int(0); --i) {
      nodes[i] = extend(s[i] - 'a');
    }
    sort((all_nodes).begin(), (all_nodes).end(),
         [](Node* x, Node* y) { return x->len < y->len; });
    for (Node* p : all_nodes) p->f->children.push_back(p);
    vector<int> arr;
    const function<void(Node*)> dfs = [&](Node* p) {
      p->label = static_cast<int>((arr).size());
      arr.push_back(p->len);
      for (Node* q : p->children) {
        dfs(q);
        arr.push_back(p->len);
      }
    };
    dfs(root);
    rmq.init(arr);
  }
  int query(int i, int j) const {
    if (i == j) return 1 << 20;
    i = nodes[i]->label;
    j = nodes[j]->label;
    if (i > j) swap(i, j);
    return rmq.query(i, j + 1);
  }
};
vector<int> compute_ranks(const string& s, const string& t) {
  const string str = s + t;
  LCP* lcp = new LCP(str);
  const auto make = [&](int i) {
    vector<pair<int, int> > r;
    if (i < static_cast<int>((s).size()))
      r.push_back(make_pair(i, static_cast<int>((s).size())));
    r.push_back(make_pair(static_cast<int>((s).size()),
                          static_cast<int>((str).size())));
    if (i > 0) r.push_back(make_pair(0, i));
    return r;
  };
  const auto compare = [&](int i, int j) {
    vector<pair<int, int> > x = make(i), y = make(j);
    while (!x.empty() && !y.empty()) {
      int xi = x.back().first, xlen = x.back().second - xi;
      int yi = y.back().first, ylen = y.back().second - yi;
      int len = lcp->query(xi, yi);
      if (len < min(xlen, ylen)) {
        return str[xi + len] < str[yi + len];
      }
      if (xlen <= ylen)
        x.pop_back();
      else
        x.back().first += ylen;
      if (ylen <= xlen)
        y.pop_back();
      else
        y.back().first += xlen;
    }
    return i < j;
  };
  vector<int> is(static_cast<int>((s).size()) + 1);
  iota((is).begin(), (is).end(), 0);
  sort((is).begin(), (is).end(), compare);
  vector<int> ranks(static_cast<int>((s).size()) + 1);
  for (int i = int(0); i <= int((static_cast<int>((s).size()) + 1) - 1); ++i)
    ranks[is[i]] = i;
  return ranks;
}
int up_to_mod(int i, int a, int b) {
  int delta = b - i % a;
  if (delta < 0) delta += a;
  return i + delta;
}
int down_to_mod(int i, int a, int b) {
  int delta = i % a - b;
  if (delta < 0) delta += a;
  return i - delta;
}
void solve(vector<int> a) {
  const int N = 100001;
  vector<int> index(static_cast<int>((a).size()));
  for (int i = int(0); i <= int((static_cast<int>((a).size())) - 1); ++i)
    index[a[i]] = i;
  static RMQ<N> large;
  large.init(a);
  const int kSmall = 80;
  int qn;
  scanf("%d", &qn);
  struct Query {
    int l, r, k, x, y;
    int ans = 1 << 30;
    void read() { scanf("%d%d%d%d%d", &l, &r, &k, &x, &y); }
  };
  vector<Query> qs(qn);
  for (Query& q : qs) {
    q.read();
    if (q.k >= kSmall) {
      while (q.x < static_cast<int>((a).size())) {
        int l0 = max(q.l, q.x), r0 = min(q.r, q.y);
        if (l0 <= r0) {
          setmin(q.ans, large.query(l0, r0 + 1));
        }
        q.x += q.k, q.y += q.k;
      }
    }
  }
  for (int k = int(1); k <= int((kSmall)-1); ++k) {
    static int b[N], pos[N];
    int cur = 0;
    for (int i = int(0); i <= int((k)-1); ++i) {
      for (int j = i; j < static_cast<int>((a).size()); j += k) {
        b[cur] = a[j];
        pos[j] = cur;
        ++cur;
      }
    }
    static RMQ<N> rmq;
    rmq.init(b, cur);
    for (Query& q : qs)
      if (q.k == k) {
        for (int i = int(q.x); i <= int(q.y); ++i) {
          int l0 = up_to_mod(q.l, k, i);
          int r0 = down_to_mod(q.r, k, i);
          if (l0 <= r0) {
            setmin(q.ans, rmq.query(pos[l0], pos[r0] + 1));
          }
        }
      }
  }
  for (const auto& q : qs) {
    if (q.ans < static_cast<int>((a).size()))
      printf("%d ", index[q.ans]);
    else
      printf("-1 ");
  }
  printf("\n");
}
int main() {
  static char buf[100010];
  scanf("%s", buf);
  string s(buf);
  scanf("%s", buf);
  string t(buf);
  vector<int> ranks = compute_ranks(s, t);
  solve(ranks);
  return 0;
}
