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;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '{';
  for (int i = (0), __i = (((int)(vec).size())); i < __i; i++) {
    os << vec[i];
    if (i + 1 != ((int)(vec).size())) os << ',';
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &par) {
  os << '(' << par.first << ',' << par.second << ')';
  return os;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
template <class T>
T sqr(T x) {
  return x * x;
}
const long long MOD = 1e9 + 7;
long long bin_pow(long long base, long long p) {
  if (p == 1) return base;
  if (p % 2 == 0) {
    long long t = bin_pow(base, p / 2);
    return t * t % MOD;
  } else
    return bin_pow(base, p - 1) * base % MOD;
}
long long inverse_element(long long x) { return bin_pow(x, MOD - 2); }
long long add(long long a, long long b) { return (a + b) % MOD; }
long long sub(long long a, long long b) { return (MOD + a - b) % MOD; }
long long divide(long long a, long long b) {
  return a * inverse_element(b) % MOD;
}
long long mult(long long a, long long b) { return (a * b) % MOD; }
int sBC[101010];
int tBC[101010];
int sEA[101010];
int tEA[101010];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  int slen = s.length();
  int tlen = t.length();
  for (int i = (0), __i = (slen); i < __i; i++) {
    sEA[i] = (s[i] != 'A' ? 0 : (i > 0 ? sEA[i - 1] + 1 : 1));
    sBC[i] = (i > 0 ? sBC[i - 1] : 0) + (s[i] != 'A');
  }
  for (int i = (0), __i = (tlen); i < __i; i++) {
    tEA[i] = (t[i] != 'A' ? 0 : (i > 0 ? tEA[i - 1] + 1 : 1));
    tBC[i] = (i > 0 ? tBC[i - 1] : 0) + (t[i] != 'A');
  }
  int Q;
  cin >> Q;
  string res = "";
  for (int q = (0), __q = (Q); q < __q; q++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int scnt = sBC[b - 1] - (a > 1 ? sBC[a - 2] : 0);
    int tcnt = tBC[d - 1] - (c > 1 ? tBC[c - 2] : 0);
    int sea = min(sEA[b - 1], b - a + 1);
    int tea = min(tEA[d - 1], d - c + 1);
    if (scnt == 0 && tcnt > 0) {
      sea--;
      if (sea > tea) sea = tea;
      scnt = 2;
    }
    if (tea <= sea && ((tea % 3) == (sea % 3) || tcnt > scnt) && tcnt >= scnt &&
        ((scnt & 1) == (tcnt & 1)))
      res += '1';
    else
      res += '0';
  }
  cout << res;
  return 0;
}
