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 $\rightarrow$ BC  B $\rightarrow$ AC  C $\rightarrow$ AB  AAA $\rightarrow$ 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| ≤ 10^5). The second line contains a string T (1 ≤ |T| ≤ 10^5), 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 ≤ 10^5).

The following Q lines describe queries. The i-th of these lines contains four space separated integers a_{i}, b_{i}, c_{i}, d_{i}. These represent the i-th query: is it possible to create T[c_{i}..d_{i}] from S[a_{i}..b_{i}] 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 $A A B \rightarrow A A A C \rightarrow \operatorname{AAA} A B \rightarrow A B$.

The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.

Difficulty: interview

Starter code:

Solutions:
# python3
import sys


def read_all_following_lines():
    lines = sys.stdin.readlines()
    return (tuple(map(int, line.split())) for line in lines)


class AbcString(object):
    def __init__(self, string):
        self.prefix_bc = [0]
        self.a_strike = [0]

        bc, strike = 0, 0
        for symbol in string:
            if symbol == 'A':
                strike += 1
            else:
                strike = 0
                bc += 1
            self.prefix_bc.append(bc)
            self.a_strike.append(strike)

    def get_info(self, begin, end):
        bc = self.prefix_bc[end] - self.prefix_bc[begin]
        trailing_a = min(self.a_strike[end], end - begin)
        return bc, trailing_a


def can_mutate(start, finish):
    from_bc, from_a = start
    to_bc, to_a = finish

    if (from_bc & 1) != (to_bc & 1): return False
    if from_bc > to_bc: return False
    if from_a < to_a: return False

    if from_bc == to_bc: return (from_a - to_a) % 3 == 0
    if from_a == to_a: return from_bc != 0

    # from_bc < to_bc
    # from_a > to_a
    return True


def main():
    s = AbcString(input())
    t = AbcString(input())
    input()  # skip one line
    requests = read_all_following_lines()

    answer = ""
    for (a, b, c, d) in requests:
        can = can_mutate(s.get_info(a - 1, b), t.get_info(c - 1, d))
        answer += "1" if can else "0"

    print(answer)


main()


def read():
    s = input()
    l = len(s)
    r = [[0] * (l + 1), [0] * (l + 1)]
    for i in range(l):
        r[0][i + 1] = (r[0][i] + 1) * (s[i] == 'A')
        r[1][i + 1] = r[1][i] + (s[i] != 'A')
    return r
s, t = read(), read()
q = int(input())
r = ''
for i in range(q):
    a, b, c, d = list(map(int, input().split()))
    sb = s[1][b] - s[1][a] + (s[0][a] == 0)
    sa = s[0][b] - (s[0][a] - 1) * (sb == 0)
    tb = t[1][d] - t[1][c] + (t[0][c] == 0)
    ta = t[0][d] - (t[0][c] - 1) * (tb == 0)
    if any([sb > tb, sa < ta, tb - sb & 1, sb == tb and (sa - ta) % 3, sa == ta and not sb and tb]):
        r += '0'
    else:
        r += '1'
print(r)


def main():
    s, t = input(), input()
    s_info, t_info = fast_counter(s), fast_counter(t)
    
    queries = int(input())
    answer = ''
    for _ in range(queries):
        l1, r1, l2, r2 = list(map(int, input().split()))
        l1, l2 = l1 - 1, l2 - 1

        from_mask = (s_info[1][r1] - s_info[1][l1], min(r1 - l1, s_info[0][r1]))
        to_mask = (t_info[1][r2] - t_info[1][l2], min(r2 - l2, t_info[0][r2]))

        if can_transform(from_mask, to_mask):
            answer += '1'
        else:
            answer += '0'

    print(answer)


def can_transform(from_mask, to_mask):
    if from_mask[0] > to_mask[0]:
        return False
    elif (to_mask[0] - from_mask[0]) % 2 != 0:
        return False
    elif to_mask[0] == from_mask[0]:
        if to_mask[1] > from_mask[1]:
            return False
        return (from_mask[1] - to_mask[1]) % 3 == 0
    elif from_mask[0] == 0:
        return to_mask[1] < from_mask[1]
    else:
        return to_mask[1] <= from_mask[1]


def mask(l, r, info):
    return (info[1][r] - info[1][l], min(r - l, info[0][r]))


def fast_counter(s):
    a_last, b_count = [0], [0]
    for c in s:
        if c == 'A':
            a_last.append(a_last[-1] + 1)
            b_count.append(b_count[-1])
        else:
            a_last.append(0)
            b_count.append(b_count[-1] + 1)
    return (a_last, b_count)
            
main()


def main():
    s, t = input(), input()
    s_info, t_info = fast_counter(s), fast_counter(t)
    
    queries = int(input())
    answer = ''
    for _ in range(queries):
        l1, r1, l2, r2 = list(map(int, input().split()))
        l1, l2 = l1 - 1, l2 - 1

        from_mask = mask(l1, r1, s_info)
        to_mask = mask(l2, r2, t_info)

        if can_transform(from_mask, to_mask):
            answer += '1'
        else:
            answer += '0'

    print(answer)


def can_transform(from_mask, to_mask):
    if from_mask[0] > to_mask[0]:
        return False
    elif (to_mask[0] - from_mask[0]) % 2 != 0:
        return False
    elif to_mask[0] == from_mask[0]:
        if to_mask[1] > from_mask[1]:
            return False
        return (from_mask[1] - to_mask[1]) % 3 == 0
    elif from_mask[0] == 0:
        return to_mask[1] < from_mask[1]
    else:
        return to_mask[1] <= from_mask[1]


def mask(l, r, info):
    return (info[1][r] - info[1][l], min(r - l, info[0][r]))


def fast_counter(s):
    a_last, b_count = [0], [0]
    for c in s:
        if c == 'A':
            a_last.append(a_last[-1] + 1)
            b_count.append(b_count[-1])
        else:
            a_last.append(0)
            b_count.append(b_count[-1] + 1)
    return (a_last, b_count)
            
main()


def main():
    s, t = input(), input()
    s_info, t_info = fast_counter(s), fast_counter(t)
    
    queries = int(input())
    answer = ''
    for _ in range(queries):
        l1, r1, l2, r2 = list(map(int, input().split()))
        l1, l2 = l1 - 1, l2 - 1

        from_mask = mask(l1, r1, s_info)
        to_mask = mask(l2, r2, t_info)

        if can_transform(from_mask, to_mask):
            answer += '1'
        else:
            answer += '0'

    print(answer)


def can_transform(from_mask, to_mask):
    if from_mask[0] > to_mask[0]:
        return False
    elif (to_mask[0] - from_mask[0]) % 2 != 0:
        return False
    elif to_mask[0] == from_mask[0]:
        if to_mask[1] > from_mask[1]:
            return False
        return (from_mask[1] - to_mask[1]) % 3 == 0
    elif from_mask[0] == 0:
        return to_mask[1] < from_mask[1]
    else:
        return to_mask[1] <= from_mask[1]


def mask(l, r, info):
    return (info[1][r] - info[1][l], min(r - l, info[0][r]))


def fast_counter(s):
    a_last, b_count = [0], [0]
    for c in s:
        if c == 'A':
            a_last.append(a_last[-1] + 1)
            b_count.append(b_count[-1])
        else:
            a_last.append(0)
            b_count.append(b_count[-1] + 1)
    return (a_last, b_count)


main()


def pref_counts(string, char):
    result = [0]
    for c in string:
        result.append(result[-1] + (c == char))
    return result

def left_counts(string, char):
    result = [0]
    for c in string:
        result.append(result[-1] + 1 if c == char else 0)
    return result

s = input().replace("C", "B")
t = input().replace("C", "B")
s_bcounts, t_bcounts = pref_counts(s, "B"), pref_counts(t, "B")
s_lcounts, t_lcounts = left_counts(s, "A"), left_counts(t, "A")
for i in range(int(input())):
    a, b, c, d = list(map(int, input().split()))
    s_b = s_bcounts[b] - s_bcounts[a - 1]
    t_b = t_bcounts[d] - t_bcounts[c - 1]
    s_a = min(s_lcounts[b], b - a + 1)
    t_a = min(t_lcounts[d], d - c + 1)
    answer = False
    if s_b & 1 == t_b & 1:
        if s_b < t_b:
            answer = s_a - (s_b == 0) >= t_a
        elif s_b == t_b:
            answer = s_a >= t_a and (s_a - t_a) % 3 == 0
    print(int(answer), end = "")



def pref_counts(string, char):
    result = [0]
    for c in string:
        result.append(result[-1] + (c == char))
    return result

def left_counts(string, char):
    result = [0]
    for c in string:
        result.append(result[-1] + 1 if c == char else 0)
    return result

s = input().replace("C", "B")
t = input().replace("C", "B")
s_bcounts, t_bcounts = pref_counts(s, "B"), pref_counts(t, "B")
s_lcounts, t_lcounts = left_counts(s, "A"), left_counts(t, "A")
for i in range(int(input())):
    a, b, c, d = list(map(int, input().split()))
    s_b = s_bcounts[b] - s_bcounts[a - 1]
    t_b = t_bcounts[d] - t_bcounts[c - 1]
    s_a = min(s_lcounts[b], b - a + 1)
    t_a = min(t_lcounts[d], d - c + 1)
    answer = False
    if s_b & 1 == t_b & 1:
        if s_b < t_b:
            answer = s_a - (s_b == 0) >= t_a
        elif s_b == t_b:
            answer = s_a >= t_a and (s_a - t_a) % 3 == 0
    print(int(answer), end = "")