一 原题

E. Picking Strings time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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  BCB  ACC  ABAAA  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 Copy 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 .

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

二 分析

题意：给你两个长度不超过1e5的字符串S和T，只包含'A','B','C'。可以有4种对子串的操作：1）A->BC，2）B->AC，3）C->AB，4）AAA->empty。接着给Q个查询（Q<=1e5），每次查询指定S和T各自的一个子串，问能否使用上述四种操作把S的子串转换为T的子串。

分析：两个观察：1）操作中，BC字符的个数是不减的，而且每次增加的单位是2；2）B->C，C->B，B->AB，BA->B，所以如果两个非空串都不以A结尾，它们可转换等价于目标串中BC的个数比起始串多偶数个。所以我们可以集中考虑后缀全为A的串转换的条件，首先：1）如果目标串A后缀的长度大于起始串，无解；2）如果目标串A后缀长度大于起始串，有两种情况都可以转化，一是起始串BC的数量严格小于目标串，而是A正好多了3k个。等于的情况就不用说了，注意一下起始串全为A的特例。

三 代码

#include <cstdio> #include <cstring> #include <algorithm> using std::min; const int maxn = 1e5 + 5; char s[maxn], t[maxn]; int ls, lt, sum[4][maxn]; int main() { scanf("%s%s", s + 1, t + 1); ls = strlen(s + 1); lt = strlen(t + 1); for (int i = 1; i <= ls; i++) { sum[0][i] = (s[i] != 'A')? sum[0][i-1]+1: sum[0][i-1]; sum[2][i] = (s[i] == 'A')? sum[2][i-1]+1: 0; } for (int i = 1; i <= lt; i++) { sum[1][i] = (t[i] != 'A')? sum[1][i-1]+1: sum[1][i-1]; sum[3][i] = (t[i] == 'A')? sum[3][i-1]+1: 0; } int kase, a, b, c, d; scanf("%d", &kase); while (kase--) { scanf("%d%d%d%d", &a, &b, &c, &d); int x = sum[0][b] - sum[0][a-1]; int y = sum[1][d] - sum[1][c-1]; int z = min(sum[2][b], b - a + 1); int w = min(sum[3][d], d - c + 1); // number of B and C can only increase by 2 if (x > y || (y - x) % 2 != 0) { printf("0"); continue; } // take care of case when string is all A if (z < w) printf("0"); else if (z == w) { if (z == (b-a+1) && w != (d-c+1)) printf("0"); else printf("1"); } else { if ((y - x) / 2 != 0) printf("1"); else if ((z - w) % 3 == 0) printf("1"); else printf("0"); } } return 0; }