Picking Strings
Contest: VK Cup 2018 - Round 1
Difficulty rating: 2500
Tags: constructive algorithms, implementation, strings

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first query we can achieve the result, for instance, by using transitions $$AAB \rightarrow AAAC \rightarrow AAAAB \rightarrow AB$$.

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

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

Example output:
10011

Editorial:
First note that B can be always changed to C and vice versa: $$\overrightarrow { B } \rightarrow \overrightarrow { A C } \rightarrow \overrightarrow { A A _ { 1 } } \rightarrow \overrightarrow { C _ { 1 } }$$. Hence we can replace all C's with B's.
Furthermore, see that: $$\overrightarrow { AB } \rightarrow \overrightarrow { AC } \rightarrow \overrightarrow { AA_{ 1 } } \rightarrow \overrightarrow { B }$$.
The above implies the set of following rules:
• $$A \rightarrow B B$$
• $$B \rightarrow AB$$
• $$\overrightarrow{AB} \to \overrightarrow{B}$$
• $$AAA \rightarrow \text{empty string}$$
We can translate these rules to the following:
• the number of Bs can be increased by any non-negative even number
• the number of As before any B may change arbitrarily
The only remaining thing is to determine what should happen to the number of trailing A's. There are three cases:
• The number of B's is the same in the source and target $$\text{The image appears to be blurred, but it seems to contain a mathematical expression or a symbol that is not clearly discernible due to the blurriness. If there was intended text or a specific formula, it would need to be re-rendered with clearer imagery.}$$ the number of trailing A's can decrease by any non-negative multiple of 3, as no application of the first rule occurs, and the second and third rule cannot affect trailing A's.
• There are some B's in the source and the number of B's increases $$\text{The image appears to be blurred, but it seems to contain a mathematical expression or a symbol that is not clearly discernible due to the blurriness. If there was intended text or a specific formula, it would need to be re-rendered with clearer imagery.}$$ the number of trailing A's can decrease by any non-negative number. To decrease the number to k, just morph the k + 1-th A from the end to BB. To keep it the same, morph any B to AB and then to BBB to introduce extra B's as needed.
• There are no B's in the source, but some B's in the target $$\text{The image appears to be blurred, but it seems to contain a mathematical expression or a symbol that is not clearly discernible due to the blurriness. If there was intended text or a specific formula, it would need to be re-rendered with clearer imagery.}$$ the number of trailing A's has to decrease by any positive integer.
It is now easy to calculate prefix sums of the B and C occurrences, and calculate the number of trailing A's for every end position. The rest is just casework.