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'.

Source: codeforces | Difficulty: VERY_HARD
Tags: String algorithms

Implementation

Constructive algorithms


Solutions:
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 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)


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
	return True

def main():
	s = AbcString(input())
	t = AbcString(input())
	input()
	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()