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”。