A. Не подстрока
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скобочная последовательность — это строка из символов «(» и/или «)». Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:

  • скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)», соответственно);
  • скобочные последовательности «)(», ( и ) — неправильные.

Вам задана скобочная последовательность $$$s$$$; обозначим ее длину за $$$n$$$. Вы должны найти такую правильную скобочную последовательность $$$t$$$ длины $$$2n$$$, что $$$s$$$ не входит в $$$t$$$ как непрерывная подстрока, или сказать, что это невозможно.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит строку $$$s$$$ ($$$2 \le |s| \le 50$$$), состоящую из символов «(» и/или «)».

Выходные данные

Для каждого набора входных данных выведите ответ на него. Если требуемой правильной скобочной последовательности не существует, выведите NO в отдельной строке. В противном случае выведите YES в первой строке, а во второй строке выведите требуемую правильную скобочную последовательность $$$t$$$. Если ответов несколько — выведите любой из них.

Пример
Входные данные
4
)(
(()
()
))()
Выходные данные
YES
(())
YES
()()()
NO
YES
()(()())