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>
struct Range {
  size_t l, r;
  auto size() const -> size_t { return r - l; }
  auto mid() const -> size_t { return (l + r) / 2; }
  auto divide() const -> std::pair<Range, Range> {
    return {{l, mid()}, {mid(), r}};
  }
  auto contains(const Range &rhs) const -> bool;
  auto disjoint(const Range &rhs) const -> bool;
};
struct STree {
  struct Node {
    const Range range;
    size_t b_count, a_last;
    std::unique_ptr<Node> left, right;
    void update() {
      b_count = left->b_count + right->b_count;
      a_last = right->a_last;
      if (right->b_count == 0) {
        a_last += left->a_last;
      }
    }
  };
  void build(Node *node, const std::string &str);
  Node root;
  STree(std::string s) : root{{0, s.size()}} { build(&root, s); }
  auto get_mask(Range &range) -> std::pair<size_t, size_t> {
    return get_mask(range, &root);
  }
  auto get_mask(Range &range, Node *node) -> std::pair<size_t, size_t>;
};
auto CanTransform(std::pair<size_t, size_t> from, std::pair<size_t, size_t> to)
    -> bool;
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::string s, t;
  std::cin >> s >> t;
  size_t queries;
  std::cin >> queries;
  STree s_tree(s), t_tree(t);
  for (size_t query = 0; query < queries; ++query) {
    Range from, to;
    std::cin >> from.l >> from.r >> to.l >> to.r;
    --from.l, --to.l;
    auto mask_from = s_tree.get_mask(from), mask_to = t_tree.get_mask(to);
    std::cout << CanTransform(mask_from, mask_to);
  }
  return 0;
}
auto STree::get_mask(Range &range, Node *node) -> std::pair<size_t, size_t> {
  if (range.disjoint(node->range)) {
    return {0, 0};
  }
  if (range.contains(node->range)) {
    return {node->b_count, node->a_last};
  }
  auto left = get_mask(range, node->left.get());
  auto right = get_mask(range, node->right.get());
  std::pair<size_t, size_t> mask{left.first + right.first, right.second};
  if (right.first == 0) {
    mask.second += left.second;
  }
  return mask;
}
void STree::build(STree::Node *node, const std::string &str) {
  if (node->range.size() == 1) {
    if (str[node->range.l] == 'A') {
      node->a_last = 1;
      node->b_count = 0;
    } else {
      node->b_count = 1;
      node->a_last = 0;
    }
    return;
  }
  auto [l_segment, r_segment] = node->range.divide();
  node->left.reset(new Node{l_segment});
  node->right.reset(new Node{r_segment});
  build(node->left.get(), str);
  build(node->right.get(), str);
  node->update();
}
auto CanTransform(std::pair<size_t, size_t> from, std::pair<size_t, size_t> to)
    -> bool {
  if (from.first > to.first) {
    return false;
  }
  if ((to.first - from.first) & 1) {
    return false;
  }
  if (from.first == to.first) {
    if (to.second > from.second) {
      return false;
    }
    return ((from.second - to.second) % 3 == 0);
  }
  if (from.first == 0) {
    return from.second > to.second;
  }
  return from.second >= to.second;
}
auto Range::contains(const Range &rhs) const -> bool {
  return l <= rhs.l && rhs.r <= r;
}
auto Range::disjoint(const Range &rhs) const -> bool {
  return rhs.r <= l || r <= rhs.l;
}
