Not a Substring (Codeforces 1860A)
Tags: Others, strings

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.


Sample Inputs:
4
)(
(()
()
))()

Sample Outputs:
YES
(())
YES
()()()
NO
YES
()(()())

Solution (Python):
p = 'YES '
for s in [*open(0)][1:]:
    n = len(s) - 1
    print(('NO', p + '(' * n + ')' * n, p + '()' * n)[-('((' in s or '))' in s) or ')(' in s])

Solution (Python):
t = int(input())
for _ in range(t):
    s = input()
    patt = ''
    if s == '()':
        print('NO')
    elif ')(' in s:
        print('YES')
        print('(' * len(s) + ')' * len(s))
    else:
        print('YES')
        print('()' * len(s))

Solution (Python):
p = 'YES '
for s in [*open(0)][1:]:
    n = len(s) - 1
    print(('NO', p + '(' * n + ')' * n, p + '()' * n)[-('((' in s or '))' in s) or ')(' in s])