CF923D Picking Strings

Alice 有一个只包含字符 'A'、'B' 和 'C' 的字符串。Bob 可以对字符串的任意子串以任意顺序、任意次数使用以下变换： - $A \rightarrow BC$ - $B \rightarrow AC$ - $C \rightarrow AB$ - $AAA \rightarrow$ 空串 注意，子串指的是一个或多个连续的字符。对于给定的若干询问，判断是否可以通过有限次上述变换，将源字符串的某一子串变为目标字符串的某一子串。

第一行包含一个字符串 $S$（$1 \leq |S| \leq 10^{5}$）。 第二行包含一个字符串 $T$（$1 \leq |T| \leq 10^{5}$），这两个字符串均只包含大写英文字母 'A'、'B' 和 'C'。 第三行包含一个整数 $Q$（$1 \leq Q \leq 10^{5}$）。 接下来的 $Q$ 行，每行包含四个用空格分隔的整数 $a_i$、$b_i$、$c_i$、$d_i$，表示第 $i$ 个询问：是否可以通过有限次上述变换，将 $S[a_i..b_i]$ 变为 $T[c_i..d_i]$？ 这里，$U[x..y]$ 表示字符串 $U$ 从第 $x$ 个字符（从 1 开始计数）到第 $y$ 个字符的子串。特别地，$U[1..|U|]$ 表示整个字符串 $U$。 保证 $1 \leq a \leq b \leq |S|$ 且 $1 \leq c \leq d \leq |T|$。

输出一个长度为 $Q$ 的字符串，第 $i$ 个字符为 '1' 表示第 $i$ 个询问的答案为“是”，为 '0' 表示答案为“否”。

在第一个询问中，我们可以通过如下变换实现目标，例如：  第三个询问要求将 AAB 变为 A —— 但在这种情况下我们无法去除字符 'B'。 由 ChatGPT 4.1 翻译