配点 : $600$ 点

問題文

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}$ にすることができるか判定してください。

制約

• $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|$

入力

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

$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 を出力せよ。

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

YES
NO
YES
NO

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

$2$ つめのクエリでは、 ABA という文字列を BBBB にできるか聞かれています。 $4$ つめのクエリでは、 BBBAAAA という文字列を BBB にできるか聞かれています。 どちらも不可能です。

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

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