Problem: There is a simple way to create hard tasks: take one simple problem as the query, and try to find an algorithm that can solve it faster than bruteforce. This kind of tasks usually appears in OI contest, and usually involves data structures.

Let's try to create a task, for example, we take the "Hamming distance problem": for two binary strings s and t with the same length, the Hamming distance between them is the number of positions at which the corresponding symbols are different. For example, the Hamming distance between "00111" and "10101" is 2 (the different symbols are marked with bold).

We use the Hamming distance problem as a query in the following way: you are given two strings a and b and several queries. Each query will be: what is the Hamming distance between two strings ap1ap1 + 1...ap1 + len - 1 and bp2bp2 + 1...bp2 + len - 1?

Note, that in this problem the strings are zero-based, that is s = s0s1... s|s| - 1.

Input

The first line contains a string a (1 ≤ |a| ≤ 200000). The second line contains a string b (1 ≤ |b| ≤ 200000). Each character of both strings is either "0" or "1".

The third line contains an integer q (1 ≤ q ≤ 400000) — the number of queries. Each of the following q lines contains three integers: p1, p2 and len (0 ≤ p1 ≤ |a| - len; 0 ≤ p2 ≤ |b| - len), these numbers denote the parameters of the current query.

Output

Output q integers — the answers for the queries.

Examples

Input

101010
11110000
3
0 0 3
2 3 4
5 7 1


Output

1
1
0


Input

10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20


Output

5
4
3
5
13

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
const int g = 3;
const int inv2 = 499122177;
const int B = 8200;
template <typename T>
inline T read() {
  register T sum = 0;
  register char cc = getchar();
  int sym = 1;
  while (cc != '-' && (cc > '9' || cc < '0')) cc = getchar();
  if (cc == '-') sym = -1, cc = getchar();
  sum = sum * 10 + cc - '0';
  cc = getchar();
  while (cc >= '0' && cc <= '9') sum = sum * 10 + cc - '0', cc = getchar();
  return sym * sum;
}
template <typename T>
inline T read(T &a) {
  a = read<T>();
  return a;
}
template <typename T, typename... Others>
inline void read(T &a, Others &...b) {
  a = read(a);
  read(b...);
}
int add(int x, int y) { return x + y >= p ? x + y - p : x + y; }
int sub(int x, int y) { return x - y < 0 ? x - y + p : x - y; }
int mul(int x, int y) { return 1ll * x * y % p; }
int fpow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
namespace NTT {
int len, rev[524288 << 2];
void init(int l) {
  len = 1;
  int bit = 0;
  while (len < l) {
    bit += 1;
    len <<= 1;
  }
  for (int i = 0; i < len; i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
void NTT(vector<int> &A, int op = 1) {
  A.resize(len);
  for (int i = 0; i < len; i++)
    if (i < rev[i]) swap(A[i], A[rev[i]]);
  for (int i = 1; i < len; i <<= 1) {
    int gi = fpow(g, (p - 1) / (i << 1));
    if (op == -1) gi = fpow(gi, p - 2);
    for (int j = 0; j < len; j += i << 1) {
      int gn = 1;
      for (int k = j; k < j + i; k++) {
        int x = A[k], y = mul(A[k + i], gn);
        A[k] = add(x, y);
        A[k + i] = sub(x, y);
        gn = mul(gn, gi);
      }
    }
  }
  if (op == -1) {
    int o = fpow(len, p - 2);
    for (int i = 0; i < len; i++) A[i] = mul(A[i], o);
  }
}
}  // namespace NTT
struct Poly {
  vector<int> v;
  Poly() { v.clear(); }
  Poly(const vector<int> &v) : v(v) {}
  Poly(initializer_list<int> init) : v(init) {}
  void clear() { v.clear(); }
  int size() const { return v.size(); }
  void resize(int len) { v.resize(len); }
  int operator[](int k) const { return k < size() ? v[k] : 0; }
  int &operator[](int k) {
    if (k >= size()) v.resize(k + 1);
    return v[k];
  }
  Poly split(int len) const {
    if (len < size()) return vector<int>(v.begin(), v.begin() + len);
    vector<int> res(v);
    res.resize(len);
    return res;
  }
  Poly operator+(const Poly &F) const {
    Poly res;
    res.resize(max(size(), F.size()));
    for (int i = 0; i < res.size(); i++) res[i] = add(operator[](i), F[i]);
    return res;
  }
  void operator+=(const Poly &F) {
    if (size() < F.size()) resize(F.size());
    int siz = F.size();
    for (int i = 0; i < siz; i++) v[i] = add(v[i], F[i]);
  }
  Poly operator-(const Poly &F) const {
    Poly res;
    res.resize(max(size(), F.size()));
    for (int i = 0; i < res.size(); i++) res[i] = sub(operator[](i), F[i]);
    return res;
  }
  void operator-=(const Poly &F) {
    if (size() < F.size()) resize(F.size());
    int siz = F.size();
    for (int i = 0; i < siz; i++) v[i] = sub(v[i], F[i]);
  }
  void operator+=(const int &x) {
    if (!size()) resize(1);
    v[0] = add(v[0], x);
  }
  Poly operator+(const int &x) const {
    Poly res = *this;
    res += x;
    return res;
  }
  void operator-=(const int &x) {
    if (!size()) resize(1);
    v[0] = sub(v[0], x);
  }
  Poly operator-(const int &x) const {
    Poly res = *this;
    res -= x;
    return res;
  }
  Poly operator*(const int &x) const {
    Poly res = *this;
    int siz = size();
    for (int i = 0; i < siz; i++) res[i] = mul(res[i], x);
    return res;
  }
  void operator*=(const int &x) {
    int siz = size();
    for (int i = 0; i < siz; i++) v[i] = mul(v[i], x);
  }
  Poly operator*(const Poly &F) const {
    int a = size(), b = F.size();
    int len = a + b - 1;
    if (1ll * a * b <= 100) {
      Poly res;
      res.resize(len);
      for (int i = 0; i < a; i++)
        for (int j = 0; j < b; j++)
          res[i + j] = add(res[i + j], mul(v[i], F[j]));
      return res;
    }
    Poly res = *this, tmp = F;
    NTT::init(len);
    NTT::NTT(res.v);
    NTT::NTT(tmp.v);
    for (int i = 0; i < NTT::len; i++) res[i] = mul(res[i], tmp[i]);
    NTT::NTT(res.v, -1);
    res.resize(len);
    return res;
  }
  void operator*=(const Poly &F) { *this = *this * F; }
  Poly __Inv(int n) const {
    if (n == 1) return vector<int>{fpow(v[0], p - 2)};
    Poly res = __Inv((n + 1) >> 1);
    Poly H = split(n);
    NTT::init(n << 1);
    NTT::NTT(res.v);
    NTT::NTT(H.v);
    for (int i = 0; i < NTT::len; i++)
      res[i] = mul(sub(2, mul(res[i], H[i])), res[i]);
    NTT::NTT(res.v, -1);
    res.resize(n);
    return res;
  }
  Poly Inv(int n = -1) const {
    if (n == -1) n = size();
    return __Inv(n);
  }
  void Reverse() { reverse(v.begin(), v.end()); }
  Poly operator/(const Poly &F) const {
    Poly H = F, G = *this;
    H.Reverse();
    G.Reverse();
    int len = size() - F.size() + 1;
    H.resize(len);
    H = H.Inv();
    G = G * H;
    G.resize(len);
    G.Reverse();
    return G;
  }
  void operator/=(const Poly &F) { *this = *this / F; }
  Poly operator%(const Poly &F) const {
    Poly G = *this / F;
    G *= F;
    G = *this - G;
    G.resize(F.size() - 1);
    return G;
  }
  void operator%=(const Poly &F) { *this = *this % F; }
  Poly Deriv() const {
    Poly res;
    int siz = size() - 1;
    for (int i = 0; i < siz; i++) res.v.push_back(mul(i + 1, v[i + 1]));
    return res;
  }
  Poly Inte() {
    Poly res, inv;
    int siz = size();
    inv.resize(siz);
    inv[1] = 1;
    for (int i = 2; i < siz; i++) inv[i] = mul(p - p / i, inv[p % i]);
    res.v.push_back(0);
    for (int i = 1; i < siz; i++) res.v.push_back(mul(inv[i], v[i - 1]));
    return res;
  }
  Poly Ln(int n = -1) const {
    if (n == -1) n = size();
    Poly res = Deriv() * Inv(n);
    res.resize(n);
    return res.Inte();
  }
  Poly __Exp(int n) const {
    if (n == 1) return vector<int>{1};
    Poly res = __Exp((n + 1) >> 1);
    Poly G = res.Ln(n), H = split(n);
    G[0] = sub(add(v[0], 1), G[0]);
    for (int i = 1; i < n; i++) G[i] = sub(v[i], G[i]);
    res *= G;
    res.resize(n);
    return res;
  }
  Poly Exp(int n = -1) const {
    if (n == -1) n = size();
    return __Exp(n);
  }
  Poly Pow(int x, int n = -1) const {
    if (n == -1) n = size();
    return (Ln(n) * x).Exp(n);
  }
  void push(int x) { v.push_back(x); }
  void out() {
    for (auto i : v) printf("%d ", i);
    putchar('\n');
  }
  Poly Div(int x, int n = -1) {
    if (n == -1) n = size();
    Poly res;
    res.resize(n);
    int siz = size();
    for (int i = 0; i < siz && i * x < n; i++) res[i * x] = v[i];
    return res;
  }
  Poly operator<<(const int &x) const {
    Poly res;
    int siz = size() + x;
    res.resize(siz);
    for (int i = siz - 1; i >= x; i--) res[i] = v[i - x];
    return res;
  }
  void operator<<=(const int &x) {
    int siz = size() + x;
    for (int i = siz - 1; i >= x; i--) v[i] = v[i - x];
    resize(siz);
  }
  Poly operator>>(const int &x) const {
    Poly res;
    int siz = size() - x;
    res.resize(siz);
    for (int i = 0; i < siz; i++) res[i] = v[i + x];
    return res;
  }
  friend Poly operator+(const int &x, const Poly &F) { return F + x; }
  friend Poly operator-(const int &x, const Poly &F) { return F - x; }
  friend Poly operator*(const int &x, const Poly &F) { return F * x; }
  friend Poly operator/(const int &x, const Poly &F) {
    return F * fpow(x, p - 2);
  }
} F, G;
int m, ls, lt, tot, blk[524288], Len[80], ans[80][524288];
char s[524288], t[524288];
int query(int ps, int pt) {
  int res = 0;
  if (ps + B >= ls || pt + B >= lt) {
    while (ps < ls && pt < lt) {
      res += s[ps] == t[pt];
      ps += 1;
      pt += 1;
    }
    return res;
  }
  while (blk[pt] == blk[pt - 1]) {
    res += s[ps] == t[pt];
    ps += 1;
    pt += 1;
  }
  res += ans[blk[pt]][ps];
  return res;
}
int main() {
  scanf("%s%s", s, t);
  ls = strlen(s), lt = strlen(t);
  F.resize(ls);
  for (int i = 0; i < ls; i++) F[i] = s[i] == '0' ? 1 : p - 1;
  G.resize(lt);
  for (int i = 0; i < lt; i++) {
    if (i % B == 0) Len[++tot] = lt - i;
    blk[i] = tot;
    G[lt - 1 - i] = t[i] == '0' ? 1 : p - 1;
  }
  for (int i = 1; i <= tot; i++) {
    Poly a = F * G.split(Len[i]);
    for (int j = 0; j < ls; j++) {
      ans[i][j] = add(a[j + Len[i] - 1], min(Len[i], ls - j));
      ans[i][j] = mul(ans[i][j], inv2);
    }
  }
  read(m);
  for (int i = 1; i <= m; i++) {
    int ps, pt, len;
    read(ps, pt, len);
    printf("%d\n", len - query(ps, pt) + query(ps + len, pt + len));
  }
  return 0;
}