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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png" style="max-width: 100.0%;max-height: 100.0%;"/> BC -  B <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png" style="max-width: 100.0%;max-height: 100.0%;"/> AC -  C <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png" style="max-width: 100.0%;max-height: 100.0%;"/> AB -  AAA <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png" style="max-width: 100.0%;max-height: 100.0%;"/> 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.
The first line contains a string *S* (1 ≤ |*S*| ≤ 10<sup class="upper-index">5</sup>). The second line contains a string *T* (1 ≤ |*T*| ≤ 10<sup class="upper-index">5</sup>), 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<sup class="upper-index">5</sup>).

The following *Q* lines describe queries. The *i*-th of these lines contains four space separated integers *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>. These represent the *i*-th query: is it possible to create *T*[*c*<sub class="lower-index">*i*</sub>..*d*<sub class="lower-index">*i*</sub>] from *S*[*a*<sub class="lower-index">*i*</sub>..*b*<sub class="lower-index">*i*</sub>] 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*|.
In the first query we can achieve the result, for instance, by using transitions <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/2c164f8b6e335aa51b97bbd019ca0d7326927314.png" style="max-width: 100.0%;max-height: 100.0%;"/>.

The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.
#!/usr/bin/env python3

import sys
sread = sys.stdin.readline

S = sread().strip()
T = sread().strip()
Q = int(sread().strip())
Qis = [tuple(map(int, sread().strip().split())) for _ in range(Q)]

def poss(s, t):
	sA = s.count('A')
	sB = s.count('B')
	sC = s.count('C')
	tA = t.count('A')
	tB = t.count('B')
	tC = t.count('C')
	srA = len(s) - len(s.rstrip('A'))
	trA = len(t) - len(t.rstrip('A'))
	d = tB + tC - (sB + sC)
	drA = trA - srA
	return (d >= 0) and (d % 2 == 0) and (drA <= 0) and (drA % 3 == 0)



res = [poss(S[a-1:b], T[c-1:d]) for a, b, c, d in Qis]

print (''.join(map(str, map(int, res))))
