AT_arc181_b [ARC181B] Annoying String Problem

[problemUrl]: https://atcoder.jp/contests/arc181/tasks/arc181_b 英小文字からなる文字列 $ S,T $ および `0`, `1` からなる文字列 $ X $ に対し、英小文字からなる文字列 $ f(S,T,X) $ を以下のように定めます。 - 空文字列に対し、 $ i=1,2,\dots,|X| $ の順に、 $ X $ の $ i $ 文字目が `0` なら $ S $ を、 `1` なら $ T $ を末尾に結合することで得られる文字列 英小文字からなる文字列 $ S $ および `0`, `1` からなる文字列 $ X,Y $ が与えられます。 英小文字からなる文字列 $ T $ （空文字列でもよい）であって、 $ f(S,T,X)=f(S,T,Y) $ が成り立つようなものが存在するか判定してください。 $ t $ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ t $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_t $ 各ケースは以下の形式で与えられる。 > $ S $ $ X $ $ Y $

$ t $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、条件を満たす $ T $ が存在するならば `Yes` を、存在しないならば `No` を出力せよ。

### 制約 - $ 1\ \leq\ t\ \leq\ 5\ \times\ 10^5 $ - $ 1\ \leq\ |S|\ \leq\ 5\times\ 10^5 $ - $ 1\ \leq\ |X|,|Y|\ \leq\ 5\times\ 10^5 $ - $ S $ は英小文字からなる文字列 - $ X,Y $ は `0`, `1` からなる文字列 - $ 1 $ つの入力に含まれるテストケースについて、 $ |S| $ の総和は $ 5\ \times\ 10^5 $ 以下 - $ 1 $ つの入力に含まれるテストケースについて、 $ |X| $ の総和は $ 5\ \times\ 10^5 $ 以下 - $ 1 $ つの入力に含まれるテストケースについて、 $ |Y| $ の総和は $ 5\ \times\ 10^5 $ 以下 ### Sample Explanation 1 以下、文字列の結合を $ + $ を用いて表します。 $ 1 $ 番目のテストケースについて、 $ T= $`ara` とすると $ f(S,T,X)=S+T= $`araaraara` $ ,\ f(S,T,Y)=T+T+T= $`araaraara` となるため、 $ f(S,T,X)=f(S,T,Y) $ が成り立ちます。 $ 2,3 $ 番目のテストケースについて、条件を満たす $ T $ は存在しません。 ### Sample Explanation 2 $ T $ は空文字列であっても構いません。