AT_s8pc_5_c Two Parentheses

[problemUrl]: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_c E869120 と square1001 は, **同じ長さの**「正しい括弧列」を持っていました. 「正しい括弧列」とは、以下のような文字列を指す. - `()` は正しい括弧列である. - $ X $ が正しい括弧列であるとき, `(`, $ X $、`)` をこの順につなげたものは正しい括弧列である. - $ X $、$ Y $ が正しい括弧列であるとき, $ X $ と $ Y $ をこの順につなげたものは正しい括弧列である. - それ以外の括弧列は正しくない. ここでは, E869120 の持つ括弧列を $ A $, square1001 の持つ括弧列を $ B $ とする. chokudai は $ A $, $ B $ に対して以下の操作を行った. - $ B $ の各文字について, `(` であれば `)`, `)` であれば `(` に変えた. その後文字列 $ C $ (最初は空文字列) を定義し, 以下の $ 2 $ 種類の操作のいずれかを $ A $, $ B $ が両方空文字列となるまで繰り返した. - 文字列 $ C $ の末尾に $ A $ の先頭の一文字を挿入し, その後 $ A $ の先頭の一文字を削除する. - 文字列 $ C $ の末尾に $ B $ の先頭の一文字を挿入し, その後 $ B $ の先頭の一文字を削除する. 文字列 $ S $ が与えられる. $ S=C $ となる場合があり得るか, `Yes` か `No` か判定しなさい.

入力は以下の形式で標準入力から与えられる. **ただし, $ Q $ 回の質問に答えなければならないことに注意せよ. $ i $ 回目の質問における $ S $ は、ここでは $ S_i $ である.** > $ Q $ $ S_1 $ $ S_2 $ : $ S_Q $

$ Q $ 行出力せよ. $ i $ 行目には, $ i $ 回目の質問に対し, $ S=C $ となるような場合が存在するか, `Yes` か `No` を出力すること.

### 制約 - $ Q $ は $ 1 $ 以上 $ 50 $ 以下の整数. - $ S_i $ は $ 1 $ 以上 $ 20\ 000 $ 文字以内の `(`, `)` から成る文字列. - $ S_i $ の長さは $ 4 $ の倍数である. ### 小課題 小課題 $ 1 $ \[$ 90 $ 点\] - $ |S|\ \leq\ 16 $ を満たす. 小課題 $ 2 $ \[$ 100 $ 点\] - $ |S|\ \leq\ 50 $ を満たす. 小課題 $ 3 $ \[$ 310 $ 点\] - 追加の制約はない. ### Sample Explanation 1 例えば, 2 回目の質問 ($ S_2 $) では, $ A $ = "()", $ B $ = ")(" であり, `BAAB` の順番で $ C $ に挿入すれば, $ C= $ `)()(` となる. その場合, $ A $, $ B $, $ C $ は以下のように遷移する. - $ A $ = "()", $ B $ = ")(", $ C $ = "" - $ A $ = "()", $ B $ = "(", $ C $ = ")" - $ A $ = ")", $ B $ = "(", $ C $ = ")(" - $ A $ = "", $ B $ = "(", $ C $ = ")()" - $ A $ = "", $ B $ = "", $ C $ = ")()(" ### Sample Explanation 2 このケースでは、`(` が $ 5 $ 個, `)` が $ 3 $ 個存在する. 括弧列は `(` と `)` が同じ個数存在するので, これが $ S=C $ となることはあり得ない.