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;
int const nmax = 200000;
int sum[1 + nmax], last[1 + nmax];
int sum2[1 + nmax], last2[1 + nmax];
pair<int, int> extract(int from, int to) {
  return {sum[to] - sum[from - 1], to - max(last[to], from - 1)};
}
pair<int, int> extract2(int from, int to) {
  return {sum2[to] - sum2[from - 1], to - max(last2[to], from - 1)};
}
bool canget(pair<int, int> f, pair<int, int> f2) {
  if (f.first < 0 || f.second < 0 || f2.first < 0 || f2.second < 0) return 0;
  if (f.first == 0 && 0 < f2.first) {
    if (f2.second < f.second) {
      f.second = f2.second;
      f.first += 2;
      return canget(f, f2);
    } else
      return 0;
  }
  if (f.second == f2.second)
    return ((f.first <= f2.first) && (f2.first % 2 == f.first % 2));
  else if (f.second < f2.second) {
    return 0;
  } else if (f.second % 3 == f2.second % 3) {
    f.second -= (f.second - f2.second);
    return canget(f, f2);
  } else {
    f.second = f2.second;
    f.first += 2;
    return canget(f, f2);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s, t;
  cin >> s >> t;
  s = "#" + s;
  t = "#" + t;
  for (int i = 1; i < s.size(); i++) {
    if (s[i] != 'A') {
      sum[i] = 1;
      last[i] = i;
    }
    sum[i] += sum[i - 1];
    last[i] = max(last[i - 1], last[i]);
  }
  for (int i = 1; i < t.size(); i++) {
    if (t[i] != 'A') {
      sum2[i] = 1;
      last2[i] = i;
    }
    sum2[i] += sum2[i - 1];
    last2[i] = max(last2[i - 1], last2[i]);
  }
  int q;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << canget(extract(a, b), extract2(c, d));
  }
  return 0;
}
