← 返回题目列表

Codeforces · 923/D

D. 拨弦

中文机器翻译题面 查看原题

Alice 有一个由字符“A”、“B”和“C”组成的字符串。 Bob 可以以任意顺序对字符串的任意子字符串使用以下转换任意次数:

- A $$\rightarrow$$ BC
- B $$\rightarrow$$ AC
- C $$\rightarrow$$ AB
- AAA $$\rightarrow$$ 空字符串

请注意,子字符串是一个或多个连续字符。对于给定的查询,确定是否可以从源获取目标字符串。

输入

第一行包含字符串 S (1 ≤ |S| ≤ 105)。第二行包含一个字符串 T (1 ≤ |T| ≤ 105),每个字符串仅由大写英文字母 'A'、'B' 和 'C' 组成。

第三行包含查询数量 Q (1 ≤ Q ≤ 105)。

以下 Q 行描述查询。这些行的第 i 行包含四个空格分隔的整数 ai、bi、ci、di。这些代表第 i 个查询:是否可以通过应用上述转换有限次数来从 S[ai..bi] 创建 T[ci..di]?

这里,U[x..y] 是 U 的一个子字符串,从索引 x(从 1 开始索引)开始,到索引 y 结束。特别是,U[1..|U|] 是整个字符串 U。

保证 1 ≤ a ≤ b ≤ |S|且 1 ≤ c ≤ d ≤ |T|。

输出

打印 Q 个字符的字符串,其中如果第 i 个查询的答案是肯定的,则第 i 个字符为“1”,否则为“0”。

示例

输入 #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

注意

在第一个查询中,我们可以通过使用转换 $$AAB \rightarrow AAAC \rightarrow AAAAB \rightarrow AB$$ 来获得结果。

第三个查询要求将 AAB 更改为 A - 但在这种情况下,我们无法删除字符“B”。