Picking Strings

题意翻译

给定两个由$A$,$B$,$C$组成的字符串$S$和$T$，存在四种对字符串子串（连续）的变换法则： 1. $f_1(A)=BC$ 2. $f_2(B)=AC$ 3. $f_3(C)=AB$ 4. $f_4(AAA)=\varnothing$（空串） 现在有$n$个询问，每个询问由$a,b,c,d$组成，表示询问是否能够通过若干次变换将子区间为$[a,b]$的$S$串变换为子区间为$[c,d]$的$T$串。

题目描述

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 BC - B AC - C AB - AAA  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^{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| $ .

输出格式

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.

输入输出样例

输入样例 #1

AABCCBAAB
ABCB
5
1 3 1 2
2 2 2 4
7 9 1 1
3 4 2 3
4 5 1 3

输出样例 #1

10011

说明

In the first query we can achieve the result, for instance, by using transitions . The third query asks for changing AAB to A — but in this case we are not able to get rid of the character 'B'.