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 std::cerr;
using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::fixed;
using std::ios_base;
using std::map;
using std::nth_element;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::stack;
using std::string;
using std::unordered_map;
using std::unordered_set;
using std::vector;
const int MAXN = 100005;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int64_t L_INF = 4e18;
struct Node {
  int cntA, cntB, cntC;
  int endA;
  int size;
};
int q;
string s, t;
Node treeS[4 * MAXN], treeT[4 * MAXN];
Node union_nodes(const Node& v, const Node& u) {
  int endA = u.endA;
  if (u.endA == u.size) endA += v.endA;
  return Node{v.cntA + u.cntA, v.cntB + u.cntB, v.cntC + u.cntC, endA,
              v.size + u.size};
}
void print_node(const Node& v) {
  cerr << v.cntA << ' ' << v.cntB << ' ' << v.cntC << ' ' << v.endA << ' '
       << v.size << '\n';
}
void build(int v, int tl, int tr, Node* tree, const string& str) {
  if (tr - tl == 1) {
    tree[v] =
        Node{str[tl] == 'A', str[tl] == 'B', str[tl] == 'C', str[tl] == 'A', 1};
    return;
  }
  int tm = (tl + tr) >> 1;
  build(2 * v + 1, tl, tm, tree, str);
  build(2 * v + 2, tm, tr, tree, str);
  tree[v] = union_nodes(tree[2 * v + 1], tree[2 * v + 2]);
}
Node get(int v, int tl, int tr, int l, int r, Node* tree) {
  if (tr <= l || r <= tl) {
    return Node{0, 0, 0, 0, 0};
  }
  if (l <= tl && tr <= r) {
    return tree[v];
  }
  int tm = (tl + tr) >> 1;
  Node res = union_nodes(get(2 * v + 1, tl, tm, l, r, tree),
                         get(2 * v + 2, tm, tr, l, r, tree));
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;
  cin >> s >> t;
  build(0, 0, s.size(), treeS, s);
  build(0, 0, t.size(), treeT, t);
  cin >> q;
  while (q--) {
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    l1--, l2--;
    Node v = get(0, 0, s.size(), l1, r1, treeS);
    Node u = get(0, 0, t.size(), l2, r2, treeT);
    if ((v.cntB + v.cntC) % 2 != (u.cntB + u.cntC) % 2) {
      cout << 0;
      continue;
    }
    if ((v.cntB + v.cntC) > (u.cntB + u.cntC)) {
      cout << 0;
      continue;
    }
    if (v.endA < u.endA) {
      cout << 0;
      continue;
    }
    if (v.endA == u.endA && v.cntB + v.cntC == 0 && u.cntB + u.cntC > 0) {
      cout << 0;
      continue;
    }
    if (v.endA % 3 == u.endA % 3) {
      cout << 1;
      continue;
    }
    if (v.endA > u.endA) {
      cout << (v.cntB + v.cntC < u.cntB + u.cntC ? 1 : 0);
      continue;
    }
  }
  return 0;
}
