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 MOD = 1e9 + 7;
int fx[] = {-1, +0, +1, +0, +1, +1, -1, -1, +0};
int fy[] = {+0, -1, +0, +1, +1, -1, +1, -1, +0};
int day[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template <typename T>
inline bool isLeap(T y) {
  return (y % 400 == 0) || (y % 100 ? y % 4 == 0 : false);
}
template <typename T>
inline T GCD(T a, T b) {
  a = abs(a);
  b = abs(b);
  if (a < b) swap(a, b);
  while (b) {
    a = a % b;
    swap(a, b);
  }
  return a;
}
template <typename T>
inline T EGCD(T a, T b, T &x, T &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T x1, y1;
  T d = EGCD(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
template <typename T>
inline T LCM(T x, T y) {
  T tp = GCD(x, y);
  if ((x / tp) * 1. * y > 9e18) return 9e18;
  return (x / tp) * y;
}
template <typename T>
inline T BigMod(T A, T B, T M = MOD) {
  A %= M;
  T ret = 1;
  while (B) {
    if (B & 1) ret = (ret * A) % M;
    A = (A * A) % M;
    B = B >> 1;
  }
  return ret;
}
template <typename T>
inline T InvMod(T A, T M = MOD) {
  return BigMod(A, M - 2, M);
}
template <typename T>
void Compress(T *in, int n, int f = 0) {
  vector<T> vv;
  for (int i = f; i < n + f; i++) vv.push_back(in[i]);
  sort(vv.begin(), vv.end()), vv.erase(unique(vv.begin(), vv.end()), vv.end());
  for (int i = f; i < n + f; i++)
    in[i] = lower_bound(vv.begin(), vv.end(), in[i]) - vv.begin();
}
template <typename T>
T scani(T &n) {
  n = 0;
  bool negative = false;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') negative = true;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    n = n * 10 + c - 48;
    c = getchar();
  }
  if (negative) n = ~(n - 1);
  return n;
}
template <typename T>
void write(T n, int type = true) {
  if (n < 0) {
    putchar('-');
    n = -n;
  }
  if (!n) {
    putchar('0');
    if (type == 32)
      putchar(' ');
    else if (type)
      putchar('\n');
    return;
  }
  char buff[22];
  int len = 0;
  while (n) buff[len++] = n % 10 + 48, n /= 10;
  for (int i = len - 1; i >= 0; i--) putchar(buff[i]);
  if (type == 32)
    putchar(' ');
  else if (type)
    putchar('\n');
}
int scans(char *a) {
  int i = 0;
  char c = 0;
  while (c < 33) c = getchar();
  while (c > 33) {
    a[i++] = c;
    c = getchar();
  }
  a[i] = 0;
  return i;
}
const int pSz = 2000006;
bool np[pSz + 10];
vector<int> prime;
int prime_size;
void sieve() {
  np[0] = np[1] = 1;
  prime.push_back(2);
  for (long long i = 4; i <= pSz; i += 2) np[i] = 1;
  for (long long i = 3; i <= pSz; i += 2) {
    if (!np[i]) {
      prime.push_back(i);
      for (long long j = i * i; j <= pSz; j += (i << 1)) np[j] = 1;
    }
  }
  prime_size = prime.size();
}
template <typename T>
inline T SqrDis(T x1, T y1, T x2, T y2) {
  return ((x1 - x2) * (x1 - x2)) + ((y1 - y2) * (y1 - y2));
}
template <typename T>
inline T Area2(T Ax, T Ay, T Bx, T By, T Cx, T Cy) {
  T ret = Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By);
  if (ret < 0) return ret = -ret;
  return ret;
}
const int N = 200005;
const int M = 200005;
const unsigned long long hs = 3797;
struct complx {
  double real, img;
  inline complx() { real = img = 0.0; }
  inline complx(double x) { real = x, img = 0.0; }
  inline complx(double x, double y) { real = x, img = y; }
  inline void operator+=(complx &other) {
    real += other.real, img += other.img;
  }
  inline void operator-=(complx &other) {
    real -= other.real, img -= other.img;
  }
  inline complx operator+(complx &other) {
    return complx(real + other.real, img + other.img);
  }
  inline complx operator-(complx &other) {
    return complx(real - other.real, img - other.img);
  }
  inline complx operator*(complx &other) {
    return complx((real * other.real) - (img * other.img),
                  (real * other.img) + (img * other.real));
  }
};
complx wlen_P[1048625 >> 1], A[1048625], B[1048625];
void FFT(complx *ar, int n, int inv) {
  int i, j, l, len, len2;
  const double p = 4.0 * inv * acos(0.0);
  for (i = 1, j = 0; i < n; i++) {
    for (l = n >> 1; j >= l; l >>= 1) j -= l;
    j += l;
    if (i < j) swap(ar[i], ar[j]);
  }
  for (len = 2; len <= n; len <<= 1) {
    len2 = len >> 1;
    double theta = p / len;
    complx mul(cos(theta), sin(theta));
    wlen_P[0] = complx(1, 0);
    for (i = 1; i < len2; i++) wlen_P[i] = (wlen_P[i - 1] * mul);
    for (i = 0; i < n; i += len) {
      complx t, *pu = ar + i, *pv = ar + i + len2, *pend = ar + i + len2,
                *pw = wlen_P;
      for (; pu != pend; pu++, pv++, pw++) {
        t = (*pv) * (*pw);
        *pv = *pu - t;
        *pu += t;
      }
    }
  }
  if (inv == -1) {
    double tmp = 1.0 / n;
    for (i = 0; i < n; i++) ar[i].real *= tmp;
  }
}
const int base = 7000;
int box[150][N], len[222];
char a[N + 100], b[N + 100];
int na, nb, bit[(1 << 16) + 10];
int Bta[N], Btb[N];
void print(int x) {
  string s;
  for (int i = (0); i < (32); ++i) {
    s += (x & 1) + '0';
    x /= 2;
  }
  reverse(s.begin(), s.end());
  cout << s << '\n';
}
void precal() {
  for (int i = 0; i < (1 << 16) + 1; i++) bit[i] = __builtin_popcount(i);
  for (int l = 0; l < na; l += 32)
    for (int i = 0, bi = l / 32; i < 32; i++)
      if (a[i + l] == '1') Bta[bi] |= (1ULL << i);
  for (int l = 0; l < nb; l++)
    for (int i = 0; i < 32; i++)
      if (b[i + l] == '1') Btb[l] |= (1ULL << i);
}
int bitMatch(int x, int y) {
  int ret = 0;
  unsigned short tx, ty;
  for (int i = (0); i < (2); ++i) {
    tx = x;
    ty = y;
    ret += bit[tx ^ ty];
    x >>= 16;
    y >>= 16;
  }
  return ret;
}
int ans_me(int ai, int bi, int l) {
  int ret = 0;
  int x = ai;
  int y = (ai + l - 1);
  int ix = x / 32;
  int iy = y / 32;
  if (ix == iy) {
    for (int i = (0); i < (l); ++i) ret += (a[ai + i] != b[bi + i]);
  } else {
    for (int i = (0); i < ((ix + 1) * 32 - x); ++i)
      ret += (a[ai + i] != b[bi + i]);
    for (int i = (0); i < (y - iy * 32 + 1); ++i)
      ret += (a[(ai + l - 1) - i] != b[(bi + l - 1) - i]);
    for (int i = (ix + 1); i < (iy); ++i)
      ret += bitMatch(Bta[i], Btb[bi + (i * 32 - ai)]);
  }
  return ret;
}
int main() {
  na = scans(a);
  nb = scans(b);
  precal();
  int n = 1, sz = 0;
  while (n < nb + base) n = n << 1;
  for (int i = (0); i < (nb); ++i) B[n - 1 - i] = complx(b[i] == '1' ? 1 : -1);
  FFT(B, n, 1);
  for (int bi = (0); bi < (N); ++bi) {
    if (na < base || nb < base) break;
    int ix = bi * base;
    int iy = min(na, (bi + 1) * base) - 1;
    sz = bi;
    if (ix >= na) break;
    for (int i = (0); i < (n); ++i) A[i] = complx();
    int m = (iy - ix + 1);
    len[bi] = nb - m + 1;
    for (int i = (0); i < (m); ++i) A[i] = complx(a[ix + i] == '1' ? 1 : -1);
    FFT(A, n, 1);
    for (int i = (0); i < (n); ++i) A[i] = A[i] * B[i];
    FFT(A, n, -1);
    for (int i = (0); i < (nb - m + 1); ++i)
      box[bi][i] = (m - round(A[n - 1 - i].real)) / 2;
  }
  int qr;
  scani(qr);
  while (qr--) {
    int ai, bi, l;
    scani(ai), scani(bi), scani(l);
    int x = ai;
    int y = (ai + l - 1);
    int ix = x / base;
    int iy = y / base;
    int res = 0;
    if (ix == iy || l < base) {
      res += ans_me(ai, bi, l);
    } else {
      int m = y - iy * base + 1;
      res += ans_me(ai, bi, (ix + 1) * base - x);
      res += ans_me(ai + l - m, bi + l - m, m);
      for (int i = (ix + 1); i < (iy); ++i) res += box[i][bi + (i * base - ai)];
    }
    write(res);
  }
  return 0;
}