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;
struct fast_reader {
  fast_reader &operator,(int &x) {
    scanf("%d", &x);
    return *this;
  }
  fast_reader &operator,(signed long long &x) {
    scanf(
        "%"
        "ll"
        "d",
        &x);
    return *this;
  }
  fast_reader &operator,(double &x) {
    scanf("%lf", &x);
    return *this;
  }
  fast_reader &operator,(long double &x) {
    scanf("%Lf", &x);
    return *this;
  }
  fast_reader &operator,(char &x) {
    do x = getchar();
    while (x == ' ' || x == '\n');
    return *this;
  }
  fast_reader &operator,(char *x) {
    scanf("%s", x);
    return *this;
  }
  fast_reader &operator,(string &x) {
    int c;
    do c = getchar();
    while (c == ' ' || c == '\n');
    x.clear();
    do x.push_back(c), c = getchar();
    while (c != ' ' && c != '\n' && c != EOF);
    ungetc(c, stdin);
    return *this;
  }
  fast_reader &line(string &x) {
    int c = getchar();
    x.clear();
    while (c != '\n' && c != EOF) x.push_back(c), c = getchar();
    return *this;
  }
} in;
struct fast_writer {
  fast_writer &operator,(const int x) {
    printf("%d", x);
    return *this;
  }
  fast_writer &operator,(const signed long long x) {
    printf(
        "%"
        "ll"
        "d",
        x);
    return *this;
  }
  fast_writer &operator,(const double x) {
    printf(
        "%."
        "12"
        "lf",
        x);
    return *this;
  }
  fast_writer &operator,(const long double x) {
    printf(
        "%."
        "12"
        "Lf",
        x);
    return *this;
  }
  fast_writer &operator,(const char x) {
    putchar(x);
    return *this;
  }
  fast_writer &operator,(const char *x) {
    printf("%s", x);
    return *this;
  }
  fast_writer &operator,(const string &x) { return operator,(x.c_str()); }
  fast_writer &operator-() {
    fflush(stdout);
    return *this;
  }
} out;
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline T gcd(T a, T b) {
  T c;
  while (a) c = a, a = b % a, b = c;
  return b;
}
template <class T>
inline T lcm(T a, T b) {
  return (a / gcd(a, b)) * b;
}
template <class T>
inline T pow(T a, T n, T m) {
  T b = 1;
  while (n) {
    if (n & 1) b = (b * a) % m;
    a = (a * a) % m, n >>= 1;
  }
  return b;
}
const signed long long MOD = (signed long long)1e9 + 7;
const long double EPS = (long double)1e-12;
const int N = int(1e5) + 111;
string s, t;
int q;
int a_s[N], a_t[N];
int b_s[N], b_t[N];
int main() {
  in, s, t, q;
  a_s[0] = b_s[0] = 0;
  for (int i = 0; i < s.size(); i++) {
    a_s[i + 1] = 0;
    b_s[i + 1] = b_s[i];
    if (s[i] == 'A')
      a_s[i + 1] = a_s[i] + 1;
    else
      b_s[i + 1]++;
  }
  a_t[0] = b_t[0] = 0;
  for (int i = 0; i < t.size(); i++) {
    a_t[i + 1] = 0;
    b_t[i + 1] = b_t[i];
    if (t[i] == 'A')
      a_t[i + 1] = a_t[i] + 1;
    else
      b_t[i + 1]++;
  }
  for (int i = 0; i < q; i++) {
    int l_s, r_s, l_t, r_t;
    in, l_s, r_s, l_t, r_t;
    l_s--, l_t--;
    int suf_s = min(r_s - l_s, a_s[r_s]);
    int suf_t = min(r_t - l_t, a_t[r_t]);
    int cnt_s = b_s[r_s] - b_s[l_s];
    int cnt_t = b_t[r_t] - b_t[l_t];
    if (suf_s < suf_t) {
      out, 0;
    } else {
      if ((suf_s - suf_t) % 3 > 0) cnt_s += 2;
      if ((cnt_s == 0 && cnt_t > 0 && suf_s == suf_t) || cnt_s > cnt_t ||
          (cnt_t - cnt_s) % 2 != 0) {
        out, 0;
      } else {
        out, 1;
      }
    }
  }
  exit(EXIT_SUCCESS);
}
