Alice has a string consisting of characters 'A', 'B' and 'C'. Bob can use the following transitions on any substring of our string in any order any number of times: 

  * A <image> BC
  * B <image> AC
  * C <image> AB
  * AAA <image> empty string 



Note that a substring is one or more consecutive characters. For given queries, determine whether it is possible to obtain the target string from source.

Input

The first line contains a string S (1 ≤ |S| ≤ 105). The second line contains a string T (1 ≤ |T| ≤ 105), each of these strings consists only of uppercase English letters 'A', 'B' and 'C'.

The third line contains the number of queries Q (1 ≤ Q ≤ 105).

The following Q lines describe queries. The i-th of these lines contains four space separated integers ai, bi, ci, di. These represent the i-th query: is it possible to create T[ci..di] from S[ai..bi] by applying the above transitions finite amount of times?

Here, U[x..y] is a substring of U that begins at index x (indexed from 1) and ends at index y. In particular, U[1..|U|] is the whole string U.

It is guaranteed that 1 ≤ a ≤ b ≤ |S| and 1 ≤ c ≤ d ≤ |T|.

Output

Print a string of Q characters, where the i-th character is '1' if the answer to the i-th query is positive, and '0' otherwise.

Example

Input

AABCCBAAB
ABCB
5
1 3 1 2
2 2 2 4
7 9 1 1
3 4 2 3
4 5 1 3


Output

10011

Note

In the first query we can achieve the result, for instance, by using transitions <image>.

The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U>
ostream& operator<<(ostream& o, const pair<T, U>& p) {
  o << "(" << p.first << "," << p.second << ")";
  return o;
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (T t : v) {
    o << t << ",";
  }
  o << "]";
  return o;
}
const int N = 100010;
int x[N] = {}, y[N] = {};
int xa[N] = {}, ya[N] = {};
int main() {
  string s, t;
  cin >> s >> t;
  int S = s.size(), T = t.size();
  for (int(i) = 0; (i) < (int)(S); ++(i)) {
    if (s[i] == 'B' || s[i] == 'C') {
      ++x[i + 1];
      xa[i + 1] = 0;
    } else {
      xa[i + 1] = xa[i] + 1;
    }
  }
  for (int(i) = 0; (i) < (int)(T); ++(i)) {
    if (t[i] == 'B' || t[i] == 'C') {
      ++y[i + 1];
      ya[i + 1] = 0;
    } else {
      ya[i + 1] = ya[i] + 1;
    }
  }
  for (int(i) = 0; (i) < (int)(N - 1); ++(i)) {
    x[i + 1] += x[i];
    y[i + 1] += y[i];
  }
  int Q;
  cin >> Q;
  for (int(i) = 0; (i) < (int)(Q); ++(i)) {
    int a, b, c, d;
    scanf(" %d %d %d %d", &a, &b, &c, &d);
    int ss = x[b] - x[a - 1];
    int tt = y[d] - y[c - 1];
    int ans = 0;
    if (ss <= tt) {
      if (ss == 0) {
        if (tt == 0) {
          if ((b - a) >= (d - c) && (b - a) % 3 == (d - c) % 3) ans = 1;
        } else {
          if ((b - a + 1) > ya[d] && tt % 2 == 0) ans = 1;
        }
      } else {
        if (xa[b] % 3 == ya[d] % 3) {
          if (xa[b] >= ya[d] && (tt - ss) % 2 == 0) ans = 1;
        } else {
          if (xa[b] > ya[d] && ss < tt && (tt - ss) % 2 == 0) ans = 1;
        }
      }
    }
    printf("%d", ans);
  }
  printf("\n");
  return 0;
}
