AT_arc071_c [ARC071E] TrBBnsformBBtion

[problemUrl]: https://atcoder.jp/contests/arc071/tasks/arc071_c `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` を出力せよ。

### 制約 - $ 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 $ 番目の操作で可能です。