310613: CF1860A. Not a Substring

A. Not a Substringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A bracket sequence is a string consisting of characters '(' and/or ')'. A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example:

• bracket sequences "()()" and "(())" are regular (they can be transformed into "(1)+(1)" and "((1+1)+1)", respectively);
• bracket sequences ")(", "(" and ")" are not regular.

You are given a bracket sequence $s$; let's define its length as $n$. Your task is to find a regular bracket sequence $t$ of length $2n$ such that $s$ does not occur in $t$ as a contiguous substring, or report that there is no such sequence.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The only line of each test case contains a string $s$ ($2 \le |s| \le 50$), consisting of characters "(" and/or ")".

Output

For each test case, print the answer to it. If there is no required regular bracket sequence, print NO in a separate line. Otherwise, print YES in the first line, and the required regular bracket sequence $t$ itself in the second line. If there are multiple answers — you may print any of them.

ExampleInput

4
)(
(()
()
))()

Output

YES
(())
YES
()()()
NO
YES
()(()())

题目大意：
一个括号序列是由字符 '(' 和 ')' 组成的字符串。一个规则的括号序列是指可以通过在原序列的字符之间插入 '1' 和 '+' 来转换成一个正确的算术表达式的括号序列。例如，"()()" 和 "(())" 是规则的，因为它们可以分别转换为 "(1)+(1)" 和 "((1+1)+1)"；而 ")(", "(" 和 ")" 不是规则的。

给定一个括号序列 s，长度为 n，任务是找到一个长度为 2n 的规则括号序列 t，使得 s 不作为 t 的连续子串出现，或者报告说不存在这样的序列。

输入输出数据格式：
输入：
- 第一行包含一个整数 t (1 ≤ t ≤ 1000) —— 测试用例的数量。
- 每个测试用例只有一行，包含一个字符串 s (2 ≤ |s| ≤ 50)，由字符 '(' 和 ')' 组成。

输出：
- 对于每个测试用例，输出其答案。如果不存在所需的规则括号序列，则输出一个单独的 "NO" 行。否则，先输出 "YES"，再在下一行输出所需的规则括号序列 t。如果有多个答案，可以输出其中任意一个。

示例：
输入：
```
4
)(
(()
()
))()
```
输出：
```
YES
(())
YES
()()()
NO
YES
()(()())
```

请注意，以上内容是网页内容的翻译，并未验证所提供示例的正确性或是否存在其他可能的答案。题目大意： 一个括号序列是由字符 '(' 和 ')' 组成的字符串。一个规则的括号序列是指可以通过在原序列的字符之间插入 '1' 和 '+' 来转换成一个正确的算术表达式的括号序列。例如，"()()" 和 "(())" 是规则的，因为它们可以分别转换为 "(1)+(1)" 和 "((1+1)+1)"；而 ")(", "(" 和 ")" 不是规则的。 给定一个括号序列 s，长度为 n，任务是找到一个长度为 2n 的规则括号序列 t，使得 s 不作为 t 的连续子串出现，或者报告说不存在这样的序列。 输入输出数据格式： 输入： - 第一行包含一个整数 t (1 ≤ t ≤ 1000) —— 测试用例的数量。 - 每个测试用例只有一行，包含一个字符串 s (2 ≤ |s| ≤ 50)，由字符 '(' 和 ')' 组成。 输出： - 对于每个测试用例，输出其答案。如果不存在所需的规则括号序列，则输出一个单独的 "NO" 行。否则，先输出 "YES"，再在下一行输出所需的规则括号序列 t。如果有多个答案，可以输出其中任意一个。 示例： 输入： ``` 4 )( (() () ))() ``` 输出： ``` YES (()) YES ()()() NO YES ()(()()) ``` 请注意，以上内容是网页内容的翻译，并未验证所提供示例的正确性或是否存在其他可能的答案。