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::min;
const int kN = 100010;
char s[kN], t[kN];
int l_s, l_t, q;
int s_sum_b[kN], s_suf_a[kN];
int t_sum_b[kN], t_suf_a[kN];
int main() {
  scanf("%s%s", s + 1, t + 1);
  l_s = strlen(s + 1);
  l_t = strlen(t + 1);
  for (int i = 1; i <= l_s; ++i) {
    if (s[i] == 'C') s[i] = 'B';
    if (s[i] == 'B')
      s_sum_b[i] = s_sum_b[i - 1] + 1;
    else {
      s_sum_b[i] = s_sum_b[i - 1];
      s_suf_a[i] = s_suf_a[i - 1] + 1;
    }
  }
  for (int i = 1; i <= l_t; ++i) {
    if (t[i] == 'C') t[i] = 'B';
    if (t[i] == 'B')
      t_sum_b[i] = t_sum_b[i - 1] + 1;
    else {
      t_sum_b[i] = t_sum_b[i - 1];
      t_suf_a[i] = t_suf_a[i - 1] + 1;
    }
  }
  scanf("%d", &q);
  while (q--) {
    int s_l, s_r, t_l, t_r;
    scanf("%d%d%d%d", &s_l, &s_r, &t_l, &t_r);
    int v1 = min(s_r - s_l + 1, s_suf_a[s_r]);
    int v2 = min(t_r - t_l + 1, t_suf_a[t_r]);
    if (v2 > v1)
      printf("0");
    else {
      v1 -= v2;
      int p1 = s_sum_b[s_r] - s_sum_b[s_l - 1];
      int p2 = t_sum_b[t_r] - t_sum_b[t_l - 1];
      if (p1) {
        v1 %= 3;
        v1 = min(v1, 1);
        p1 += v1 * 2;
        if (p1 <= p2 && (p1 + p2) % 2 == 0)
          printf("1");
        else
          printf("0");
      } else if (!v1)
        printf("%d", !p2);
      else {
        if (p2) {
          --v1;
          p1 += 2;
        }
        v1 %= 3;
        if (!p2) p1 += v1 * 2;
        if (p1 <= p2 && (p1 + p2) % 2 == 0)
          printf("1");
        else
          printf("0");
      }
    }
  }
}
