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;
char string_in_buffer[(int)2e6];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T kek, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(kek);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a % b == 0) return 0;
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
string s, t;
struct Dest {
  vector<int> LA;
  vector<int> BC;
  string s;
  Dest() {}
  Dest(string _s) {
    s = _s;
    int n = ((int)s.size());
    LA.resize(n, 0);
    BC.resize(n, 0);
    if (s[0] == 'A') {
      LA[0] = 1;
    }
    for (int i = 1; i < ((int)s.size()); i++) {
      if (s[i] == 'A') {
        LA[i] = LA[i - 1] + 1;
      } else {
        LA[i] = 0;
      }
    }
    bool pref = false;
    if (s[0] == 'B' || s[0] == 'C') {
      BC[0] = 1;
    }
    for (int i = 1; i < ((int)s.size()); i++) {
      BC[i] = BC[i - 1];
      if (s[i] == 'B' || s[i] == 'C') {
        BC[i]++;
      }
    }
  }
  int bc_count(int l, int r) const {
    int rez = BC[r - 1];
    if (l > 0) {
      rez -= BC[l - 1];
    }
    return rez;
  }
  int a_count(int l, int r) const {
    int rez = LA[r - 1];
    return min(r - l, rez);
  }
  friend bool query(const Dest &S, const Dest &T, pair<int, int> base,
                    pair<int, int> sub) {
    int base_bc = S.bc_count(base.first, base.second);
    int sub_bc = T.bc_count(sub.first, sub.second);
    if (base_bc > sub_bc) return false;
    if (base_bc % 2 != sub_bc % 2) return false;
    int base_a = S.a_count(base.first, base.second);
    int sub_a = T.a_count(sub.first, sub.second);
    if (base_bc == 0 && sub_bc != 0) {
      return base_a > sub_a;
    }
    if (base_a < sub_a) return false;
    int help = 0;
    {
      int a = base_a;
      int b = sub_a;
      while (a % 3 != b % 3) {
        a--;
        help++;
      }
    }
    help = min(help, 1);
    return base_bc + help * 2 <= sub_bc;
  }
};
Dest S, T;
signed main(signed argc, char *argv[]) {
  { cin, s, t; }
  {
    S = Dest(s);
    T = Dest(t);
  }
  {
    int q;
    cin, q;
    string rez;
    for (int i = 0; i < (q); i++) {
      pair<int, int> base, sub;
      cin, base, sub;
      base.first--;
      sub.first--;
      if (query(S, T, base, sub)) {
        rez.push_back('1');
      } else {
        rez.push_back('0');
      }
    }
    smart_io::precall_print();
    cout, rez;
  }
}
