Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов + и 1 можно получить из нее корректное математическое выражение. Например, последовательности (())(), () и (()(())) — правильные, в то время как )(, (() и (()))( — нет. Назовем правильную скобочную последовательность — «ПСП».
Вам задана последовательность $$$s$$$ из $$$n$$$ символов (, ) и/или ?. В этой последовательности есть ровно один символ ( и ровно один символ ).
Вам необходимо заменить каждый символ ? либо на ), либо на ( (разные символы ? могут быть заменены разными скобками). Вы не можете изменять порядок символов, удалять их, вставить другие символы, и каждый ? должен быть заменен.
Определите, возможно ли получить ПСП после этих замен.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей $$$s$$$ ($$$2 \le |s| \le 100$$$) — последовательность символов (, ) и/или ?. В этой последовательности есть ровно один символ ( и ровно один символ ).
Для каждого набора входных выведите YES, если можно получить правильную скобочную последовательность, или NO в противном случае}.
Вы можете вывести каждую букву в любом регистре (например, YES, Yes, yes, yEs будут распознаны как положительный ответ).
5 () (?) (??) ??() )?(?
YES NO YES YES NO
В первом примере последовательность уже является ПСП.
В третьем примере вы можете получить ПСП следующим образом: ()() или (()).
В четвертом примере вы можете получить ПСП следующим образом: ()().
