题目描述

A, B からなる文字列に対して、次の操作を考えます。

1. 文字列中の $1$ 文字を選ぶ。それが A なら BB で、 B なら AA で置き換える。
2. AAA か BBB であるような部分文字列を選び、消す。

例えば、ABA という文字列で $1$ 番目の操作を $1$ 文字目に対して行うと、 BBBA となります。 また、BBBAAAA に対して $2$ 番目の操作を $4$ 文字目から $6$ 文字目に対して行うと、 BBBA となります。

これらの操作を何回でも好きな順で行うことができます。

文字列 $S,T$ と $q$ 個のクエリ $a_i,\ b_i,\ c_i,\ d_i$ が与えられます。 各クエリに対して、 $S$ の部分文字列 $S_{a_i}\ S_{{a_i}+1}\ ...\ S_{b_i}$ を $T$ の部分文字列 $T_{c_i}\ T_{{c_i}+1}\ ...\ T_{d_i}$ にすることができるか判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $T$ $q$ $a_1$ $b_1$ $c_1$ $d_1$ $...$ $a_q$ $b_q$ $c_q$ $d_q$

输出格式

$q$ 行出力せよ。 $i$ 行目には、 $i$ 番目のクエリに対する答えを出力せよ。 $S_{a_i}\ S_{{a_i}+1}\ ...\ S_{b_i}$ を $T_{c_i}\ T_{{c_i}+1}\ ...\ T_{d_i}$ にすることができる場合は YES を、 できない場合は NO を出力せよ。

题目大意

题目描述

考虑对一个只含 A，B 的字符串的如下操作：

1. 将一个 A 替换成 BB，或将一个 B 替换成 AA

2. 将三个连续相同的字符（AAA 或 BBB）消掉

例如说，串 ABA 可以通过第一个操作变成 BBBA，串 BBBAAAA 可以通过第二个操作变成 BBBA.

这些操作可以以任意顺序，不限次数地进行。

给出两个串 $S$ 和 $T$，以及 $q$ 次询问 $a_i, b_i, c_i, d_i$，每次询问你需要回答 $S_{a_i...b_i}$ 这一子串是否能通过这两个操作变成 $T_{c_i...d_i}$.

输入格式

将从标准输入输出输入以下格式：

$ S $ 
$ T $ 
$ q $ 
$ a_1 $   $ b_1 $   $ c_1 $   $ d_1 $ 
$ ... $ 
$ a_q $   $ b_q $   $ c_q $   $ d_q $ 

输出格式

输出 $q$ 行，每行包含一个询问的答案。若第 $i$ 个询问 $S_{a_i...b_i}$ 这一子串能通过这两个操作变成 $T_{c_i...d_i}$，则输出 YES，否则输出 NO.

BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4

YES
NO
YES
NO

AAAAABBBBAAABBBBAAAA
BBBBAAABBBBBBAAAAABB
10
2 15 2 13
2 13 6 16
1 13 2 20
4 20 3 20
1 18 9 19
2 14 1 11
3 20 3 15
6 16 1 17
4 18 8 20
7 20 3 14

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO

提示

制約

• $1\ \leq\ |S|,\ |T|\ \leq\ 10^5$
• $S,T$ は文字A,Bからなる。
• $1\ \leq\ q\ \leq\ 10^5$
• $1\ \leq\ a_i\ \leq\ b_i\ \leq\ |S|$
• $1\ \leq\ c_i\ \leq\ d_i\ \leq\ |T|$

Sample Explanation 1

$1$ つめのクエリでは、 ABA という文字列を BBBA にできるか聞かれています。 問題文中で例に挙げたように、$1$ 番目の操作で可能です。 $2$ つめのクエリでは、 ABA という文字列を BBBB にできるか聞かれています。 $4$ つめのクエリでは、 BBBAAAA という文字列を BBB にできるか聞かれています。 どちらも不可能です。 $3$ つめのクエリでは、BBBAAAA という文字列を BBBA にできるか聞かれています。 問題文中で例に挙げたように、$2$ 番目の操作で可能です。