AT_s8pc_5_c Two Parentheses

E869120 和 square1001 各自拥有一串**等长的**“正确括号序列”。所谓“正确括号序列”是指符合下列条件的字符串： - `()` 是一个正确的括号序列。 - 如果 $X$ 是一个正确的括号序列，那么 `(`、$X$ 和 `)` 连接在一起也是一个正确的括号序列。 - 如果 $X$ 和 $Y$ 都是正确的括号序列，那么 $X$ 和 $Y$ 相连也是一个正确的括号序列。 - 其他任何括号序列都是不正确的。 设 E869120 的括号序列为 $A$，square1001 的括号序列为 $B$。chokudai 对 $A$ 和 $B$ 进行了以下操作： - 将 $B$ 中的每个 `(` 替换为 `)`，每个 `)` 替换为 `(`。然后，定义一个初始为空的字符串 $C$，并交替进行以下两种操作，直到 $A$ 和 $B$ 均为空： - 把 $A$ 的首字符移至 $C$ 的末尾，并删除 $A$ 的首字符。 - 把 $B$ 的首字符移至 $C$ 的末尾，并删除 $B$ 的首字符。 给定字符串 $S$，判断是否可能通过上述操作使得 $S = C$。如果可以，输出 `Yes`；否则输出 `No`。

输入通过标准输入给出。你需要回答 $Q$ 个问题。第 $i$ 个问题的字符串为 $S_i$。 > 第一行输入整数 $Q$，表示问题的数量。 接下来的 $Q$ 行，每行一个字符串 $S_1, S_2, \ldots, S_Q$。

输出 $Q$ 行。对于每个字符串 $S_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$ 分\] - 无额外约束。 ### 样例解释 例如，在第二个问题中，$S_2$ = `)()(`。我们可以选择 $A$ = "()", $B$ = ")("。按顺序将字符插入 $C$ 后，可以得到 $C = $ `)()(`。变化过程如下： - 初始：$A$ = "()", $B$ = ")(", $C$ = "" - 第一步：$A$ = "()", $B$ = "(", $C$ = ")" - 第二步：$A$ = ")", $B$ = "(", $C$ = ")(" - 第三步：$A$ = "", $B$ = "(", $C$ = ")()" - 第四步：$A$ = "", $B$ = "", $C$ = ")()(" 在这个过程中，每步都选择从 $A$ 或 $B$ 中取字符加入 $C$ 末尾。通过合适的选择，我们得以构造出与 $S_2$ 相同的序列。 而对于某个问题，如果 `(` 和 `)` 的数量不相等，比如 `(` 出现 $5$ 次，`)` 只出现 $3$ 次，那么根据括号序列相等原则，根本无法达成 $S = C$ 的条件。 **本翻译由 AI 自动生成**