C. Восстанови ПСП
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

В начале была некоторая ПСП. Некоторые скобки заменили на знаки вопроса. Верно ли, что существует единственный способ заменить знаки вопроса на скобки так, чтобы получилась ПСП?

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных записана ПСП с некоторыми скобками замененными на знаки вопроса. Каждый символ — это '(', ')' или '?'. Из данной последовательности можно восстановить хотя бы одну ПСП.

Суммарная длина последовательностей по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите «YES», если способ заменить знаки вопроса на скобки так, чтобы получилась ПСП, единственный. Если существует больше одного способа, то выведите «NO».

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

В первом наборе входных данных единственная возможная оригинальная ПСП — это «(())».

Во втором наборе существует несколько способов восстановить ПСП.

В третьем и четвертом наборах единственная возможная ПСП — это «()».

В пятом наборе оригинальная ПСП может быть «((()()))» или «(())()()».