A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) 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 (the resulting expressions are: "(1)+(1)" and "((1+1)+1)");

bracket sequences ")(", "(" and ")" are not.

There was an RBS. Some brackets have been replaced with question marks. Is it true that there is a unique way to replace question marks with brackets, so that the resulting sequence is an RBS?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of testcases.

The only line of each testcase contains an RBS with some brackets replaced with question marks. Each character is either '(', ')' or '?'. At least one RBS can be recovered from the given sequence.

The total length of the sequences over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print "YES" if the way to replace question marks with brackets, so that the resulting sequence is an RBS, is unique. If there is more than one way, then print "NO".


-----Examples-----

Input
5
(?))
??????
()
??
?(?)()?)
Output
YES
NO
YES
YES
NO


-----Note-----

In the first testcase, the only possible original RBS is "(())".

In the second testcase, there are multiple ways to recover an RBS.

In the third and the fourth testcases, the only possible original RBS is "()".

In the fifth testcase, the original RBS can be either "((()()))" or "(())()()".

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

String algorithms

Implementation

Constructive algorithms


Solutions:
import sys, math
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def solve():
	s = input().rstrip()
	n = len(s)
	if n % 2 == 1:
		print('NO')
		return
	c = 0
	d = 0
	idx = -1
	for i in range(n):
		if s[i] == '?':
			d += 1
		elif s[i] == '(':
			c += 1
		else:
			c -= 1
	if d % 2 != c % 2 or abs(c) > d:
		print('NO')
		return
	if d == 0:
		print('YES')
		return
	if c >= 0:
		d = (d - c) // 2
	else:
		d = (d + c) // 2 - c
	a = [0] * n
	cur = 0
	for i in range(n):
		if s[i] == '(':
			cur += 1
		elif s[i] == ')':
			cur -= 1
		elif d:
			idx = i
			cur += 1
			d -= 1
		else:
			cur -= 1
		a[i] = cur
	ok = True
	if a[idx] < 2:
		ok = False
	for i in range(idx + 1, n):
		if s[i] == '?':
			if ok:
				print('NO')
				return
			else:
				break
		elif a[i] < 2:
			ok = False
	if n % 2 == 0 and a[n - 1] >= 0:
		print('YES')
		return
	print('NO')
t = 1
t = int(input())
for i in range(1, t + 1):
	solve()


import sys
import math

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_ls():
	return list(map(int, sys.stdin.readline().strip().split()))

def test_ok(ok):
	print('YES' if ok else 'NO')

def main():
	for _ in range(int(input())):
		s = input()
		p = 0
		q = 0
		for c in s:
			if c == '(':
				p += 1
			elif c == ')':
				p -= 1
			else:
				q += 1
			if 1 - p == q:
				(q, p) = (0, 1)
		print('YES' if p == q else 'NO')
main()


import math
t = int(input())
for i in range(t):
	text = input()
	wild = 0
	pos = []
	count = 0
	if text[0] == ')' or text[-1] == '(':
		print('NO')
		continue
	for char in text[1:-1]:
		if char == '(':
			count -= 1
		if char == ')':
			count += 1
		if char == '?':
			wild += 1
		if count == wild:
			count = 0
			wild = 0
	if wild >= 2 and abs(count) != wild:
		print('NO')
	else:
		print('YES')


import math
t = int(input())
for i in range(t):
	text = input()
	q = 0
	pos = []
	count = 0
	for char in text[1:-1]:
		if char == '(':
			count -= 1
		if char == ')':
			count += 1
		if char == '?':
			q += 1
		if count == q:
			count = 0
			q = 0
	if abs(count) != q:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	count = 0
	question = 0
	for i in s:
		if i == '?':
			question += 1
		elif i == '(':
			count += 1
		else:
			count -= 1
		if count + question == 1:
			question = 0
			count = 1
	if count == question:
		print('YES')
	else:
		print('NO')


for tt in range(int(input())):
	(s, cnt, x) = (input(), 0, 0)
	for i in s:
		if i == '(':
			cnt += 1
		elif i == ')':
			cnt -= 1
		else:
			x += 1
		if 1 - cnt == x:
			x = 0
			cnt = 1
	if x == cnt:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	value = 0
	unknown = 0
	for i in s:
		if i == '(':
			value += 1
		elif i == ')':
			value -= 1
		else:
			unknown += 1
		if 1 - value == unknown:
			unknown = 0
			value = 1
	if unknown == value:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	k = 0
	l = 0
	r = 0
	x = -1
	y = -1
	for j in input():
		if j == '(':
			l += 1
			r += 1
			if x + 1:
				x += 1
				y += 1
		elif j == ')':
			if l < 1:
				l = 1
			else:
				l -= 1
			r -= 1
			if x + 1:
				if x:
					x -= 1
				else:
					x += 1
				y -= 1
		else:
			if l != r and x < 0:
				x = l + 1
				y = r - 1
			elif x + 1:
				if x:
					x -= 1
				else:
					x += 1
				y += 1
			if l < 1:
				l = 1
			else:
				l -= 1
			r += 1
		if r < 0:
			k = 1
		if y < 0:
			y = -1
			x = -1
	print(['YES', 'NO'][k or l > 0 or x == 0])


import re
for _ in ' ' * int(input()):
	(wh, z) = (0, 0)
	for i in input():
		if i == '(':
			z += 1
		elif i == ')':
			z -= 1
		elif i == '?':
			wh += 1
		if z + wh == 1:
			z = 1
			wh = 0
	if z == wh:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(s, c, x) = (input(), 0, 0)
	for i in s:
		if i == '(':
			c += 1
		elif i == ')':
			c -= 1
		else:
			x += 1
		if 1 - c == x:
			x = 0
			c = 1
	if x == c:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	o = 0
	q = 0
	for i in s:
		if i == '(':
			o += 1
		elif i == ')':
			o -= 1
		else:
			q += 1
		if 1 - o == q:
			(o, q) = (1, 0)
	print('YES' if o == q else 'NO')


in_il = lambda : list(map(int, input().split()))
in_sl = lambda : input().split()
in_i = lambda : int(input())
MAX_INT = float('inf')

def solve():
	seq = input()
	v = 0
	q = 0
	for c in seq:
		if c == '(':
			v += 1
		elif c == ')':
			v -= 1
		elif c == '?':
			q += 1
	v = -v
	open = (q + v) // 2
	close = (q - v) // 2
	if open == 0 or close == 0:
		print('YES')
		return
	done = False
	new_v = 0
	for c in seq:
		if c == '(':
			new_v += 1
		elif c == ')':
			new_v -= 1
		elif c == '?':
			if open > 0:
				if open == 1:
					if done == False:
						new_v -= 1
						close -= 1
						done = True
					else:
						new_v += 1
						open -= 1
				else:
					new_v += 1
					open -= 1
			elif close > 0:
				new_v -= 1
				close -= 1
		if new_v < 0:
			print('YES')
			return
	print('NO')
for _ in range(in_i()):
	solve()


from collections import Counter
from collections import deque
for _ in range(int(input())):
	key = input()
	cnt = 0
	q = 0
	for x in key:
		if x == '(':
			cnt += 1
		if x == ')':
			cnt -= 1
		if x == '?':
			q += 1
		if cnt + q == 1:
			cnt = 1
			q = 0
	if cnt == q:
		print('YES')
	else:
		print('NO')


tt = int(input())
for _ in range(tt):
	a = input()
	k = 0
	x = 0
	for i in range(len(a)):
		if a[i] == '(':
			k += 1
		elif a[i] == ')':
			k -= 1
		else:
			x += 1
		if x + k == 1:
			x = 0
			k = 1
	if x == k:
		print('YES')
	else:
		print('NO')


def check(s) -> bool:
	t = 0
	for c in s:
		if c == '(':
			t += 1
		elif c == ')':
			t -= 1
			if t < 0:
				return False
		else:
			assert False
	return True
for _ in range(int(input())):
	s = list(input())
	cnt = len(s) // 2 - s.count('(')
	if cnt == 0 or cnt == s.count('?'):
		print('YES')
		continue
	for i in range(len(s)):
		if s[i] != '?':
			continue
		s[i] = '(' if cnt > 1 or cnt == 0 else ')'
		cnt -= 1
	print('NO' if check(s) else 'YES')


a = int(input())
for _ in range(a):
	b = input()
	lenb = len(b)
	qmark = 0
	status = 0
	for i in range(lenb):
		if b[i] == '(':
			status += 1
		elif b[i] == ')':
			status -= 1
		else:
			qmark += 1
		if status < 0 and qmark > 0:
			qmark -= 1
			status += 1
		if status == 0 and qmark % 2 != 0:
			qmark -= 1
			status += 1
	if qmark == 0 or qmark == status:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	st = input()
	k1 = 0
	k2 = 0
	for j in range(len(st)):
		if st[j] == '?':
			k1 += 1
		elif st[j] == '(':
			k2 += 1
		else:
			k2 -= 1
		if 1 - k2 == k1:
			k1 = 0
			k2 = 1
	if k1 == abs(k2):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	x = input()
	left = 0
	question = 0
	for char in x:
		if char == '(':
			left += 1
		elif char == ')':
			left -= 1
		elif char == '?':
			question += 1
		if question + left == 1:
			question = 0
			left = 1
	if abs(left) == question:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	a = s.count('?')
	b = s.count('(')
	c = s.count(')')
	d = (a + c - b) // 2
	e = a - d
	if d * e == 0:
		print('YES')
		continue
	t = 0
	v = 0
	m = True
	for i in s:
		if i == '(':
			t += 1
		elif i == ')':
			if t == 0:
				m = False
				break
			t -= 1
		else:
			v += 1
			if v < d:
				t += 1
			elif v == d:
				if t == 0:
					m = False
					break
				t -= 1
			elif v == d + 1:
				t += 1
			else:
				t -= 1
	if m:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	str = input()
	x = 0
	y = 0
	for j in range(len(str)):
		if str[j] == '?':
			x += 1
		elif str[j] == '(':
			y += 1
		else:
			y -= 1
		if 1 - y == x:
			x = 0
			y = 1
	if x == y:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input().strip()
	n = len(s)
	left_bracket_num = n // 2
	right_bracket_num = n // 2
	for char in s:
		if char == '(':
			left_bracket_num -= 1
		elif char == ')':
			right_bracket_num -= 1
	if left_bracket_num == 0 or right_bracket_num == 0:
		print('YES')
	else:
		sum_before_qs = []
		_sum = 0
		idx = -1
		for (idx, char) in enumerate(s):
			if char == '(':
				_sum += 1
			elif char == ')':
				_sum -= 1
			else:
				sum_before_qs.append(_sum + len(sum_before_qs))
				if len(sum_before_qs) == left_bracket_num:
					break
		if sum_before_qs[-1] < 1:
			print('YES')
		else:
			current_value = sum_before_qs[-1] - 1
			while True:
				idx += 1
				if s[idx] == '?':
					print('NO')
					break
				elif s[idx] == '(':
					current_value += 1
				else:
					current_value -= 1
					if current_value < 0:
						print('YES')
						break


def solve():
	s = list(input())
	cnt = 0
	bal = 0
	n = len(s)
	for i in range(n):
		if s[i] == '?':
			cnt += 1
		elif s[i] == '(':
			bal += 1
		else:
			bal -= 1
	if cnt == abs(bal):
		print('YES')
		return
	cntPos = (cnt - bal) // 2
	placeNeg = False
	for i in range(n):
		if s[i] == '?':
			if cntPos > 1:
				s[i] = '('
				cntPos -= 1
			elif cntPos == 1:
				if placeNeg:
					s[i] = '('
					cntPos -= 1
				else:
					s[i] = ')'
					placeNeg = True
			else:
				s[i] = ')'
	bal = 0
	for i in range(n):
		if s[i] == '(':
			bal += 1
		else:
			bal -= 1
		if bal < 0:
			print('YES')
			return
	print('NO')
T = int(input())
for t in range(T):
	solve()


t = int(input())
for i in range(t):
	s = input()
	cnt = 0
	ans = 0
	for j in range(len(s)):
		if s[j] == '(':
			cnt += 1
		elif s[j] == ')':
			cnt -= 1
		else:
			ans += 1
		if cnt + ans == 1:
			ans = 0
			cnt = 1
	if abs(cnt) == ans:
		print('YES')
	else:
		print('NO')


def check(s):
	bal = 0
	for i in s:
		if i == '(':
			bal += 1
		else:
			bal -= 1
		if bal < 0:
			return False
	return bal == 0
for _ in range(int(input())):
	s = list(input())
	(op, cl) = (len(s) // 2, len(s) // 2)
	pos = []
	for i in range(len(s)):
		if s[i] == '?':
			pos.append(i)
		elif s[i] == '(':
			op -= 1
		else:
			cl -= 1
	for (index, i) in enumerate(pos):
		if index < op:
			s[i] = '('
		else:
			s[i] = ')'
	unique = True
	if op > 0 and cl > 0:
		(s[pos[op - 1]], s[pos[op]]) = (s[pos[op]], s[pos[op - 1]])
		if check(s):
			unique = False
	if unique:
		print('YES')
	else:
		print('NO')


def main():
	for t in range(int(input())):
		s = list(input())
		(a, b, c) = (0, 0, 0)
		for i in s:
			if i == '(':
				a += 1
			elif i == ')':
				b += 1
			else:
				c += 1
		if c < 2 or c == abs(a - b):
			print('YES')
			continue
		a = len(s) // 2 - a
		b = len(s) // 2 - b
		(f1, f2) = (-1, -1)
		for i in range(len(s)):
			if a == 0:
				break
			if s[i] == '?':
				s[i] = '('
				a -= 1
				if a == 0:
					f1 = i
		for i in range(len(s) - 1, -1, -1):
			if b == 0:
				break
			if s[i] == '?':
				s[i] = ')'
				b -= 1
				if b == 0:
					f2 = i
		s[f1] = '(' if s[f1] == ')' else ')'
		s[f2] = '(' if s[f2] == ')' else ')'
		flag = True
		res = []
		for i in range(len(s)):
			if s[i] == '(':
				res.append(s[i])
			elif len(res):
				res.pop(-1)
			else:
				flag = False
				break
		print('YES' if not flag else 'NO')
main()


for _ in range(int(input())):
	s = input()
	cnt = 0
	q = 0
	for item in s:
		if item == ')':
			cnt += 1
		elif item == '(':
			cnt -= 1
		else:
			q += 1
	opened = (q + cnt) // 2
	closed = (q - cnt) // 2
	if opened == 0 or closed == 0:
		print('YES')
		continue
	check = ''
	for i in range(opened - 1):
		check += '('
	check += ')'
	check += '('
	for i in range(closed - 1):
		check += ')'
	pnt = 0
	l = list(s)
	for i in range(len(s)):
		if l[i] == '?':
			l[i] = check[pnt]
			pnt += 1
	l1 = ''.join(l)
	cnt1 = 0
	flag = False
	for item in l1:
		if item == '(':
			cnt1 += 1
		elif item == ')':
			cnt1 -= 1
		if cnt1 < 0:
			flag = True
	if flag:
		print('YES')
	else:
		print('NO')


def isvalid(seq):
	s = f = 0
	for br in seq:
		if br == '(':
			s += 1
		else:
			f += 1
		if f > s:
			return False
	return s == f
for _ in range(int(input())):
	seq = [*input()]
	n = len(seq)
	seq[0] = '('
	seq[-1] = ')'
	os = of = nq = 0
	for br in seq:
		if br == '(':
			os += 1
		elif br == ')':
			of += 1
		else:
			nq += 1
	ns = (nq + of - os) // 2
	nf = (nq + os - of) // 2
	seq1 = []
	last_open = first_close = None
	for (i, br) in enumerate(seq):
		if br == '?':
			if ns:
				ns -= 1
				seq1.append('(')
				last_open = i
			else:
				nf -= 1
				seq1.append(')')
				if first_close is None:
					first_close = i
		else:
			seq1.append(br)
	if first_close is None or last_open is None:
		print('YES')
	else:
		seq2 = seq1[:]
		(seq2[last_open], seq2[first_close]) = (seq2[first_close], seq2[last_open])
		if isvalid(seq2) and seq1 != seq2:
			print('NO')
		else:
			print('YES')


for i in range(int(input())):
	s = input()
	s = [i for i in s]
	n = len(s)
	open = close = 0
	que = []
	for i in range(n):
		if s[i] == '(':
			open += 1
		elif s[i] == ')':
			close += 1
		else:
			que.append(i)
	if open == n // 2 or close == n // 2:
		print('YES')
		continue
	open = n // 2 - open
	close = n // 2 - open
	for i in range(0, open):
		s[que[i]] = '('
	for i in range(open, len(que)):
		s[que[i]] = ')'
	for i in range(len(que)):
		if s[que[i]] == ')':
			s[que[i]] = '('
			s[que[i - 1]] = ')'
			break
	stack = []
	for i in s:
		if i == ')' and stack and (stack[-1] == '('):
			stack.pop()
		else:
			stack.append(i)
	if stack:
		print('YES')
	else:
		print('NO')


def RBS(s):
	cnt = 0
	for i in s:
		if i == '(':
			cnt += 1
		if i == ')':
			cnt -= 1
		if cnt < 0:
			return False
	if cnt == 0:
		return True
	else:
		return False
for t in range(int(input())):
	s = input()
	n = len(s)
	k = []
	for i in s:
		k.append(i)
	ques = s.count('?')
	f = s.count('(')
	e = s.count(')')
	if f > e:
		extra = f - e
		fb = (ques - extra) // 2
		ef = extra + (ques - extra) // 2
	else:
		extra = e - f
		fb = extra + (ques - extra) // 2
		ef = (ques - extra) // 2
	if fb == 0 or ef == 0:
		print('YES')
	else:
		tques = ['('] * (fb - 1)
		tques.append(')')
		tques.append('(')
		for i in range(ef - 1):
			tques.append(')')
		j = 0
		for i in range(n):
			if k[i] == '?':
				k[i] = tques[j]
				j += 1
		print('NO' if RBS(k) else 'YES')


def psp(s):
	balanse = 0
	for elem in s:
		if elem == '(':
			balanse += 1
		else:
			balanse -= 1
		if balanse < 0:
			return False
	return balanse == 0

def get_answer(s):
	q_indexes = []
	for i in range(len(s)):
		if s[i] == '?':
			q_indexes.append(i)
	close = s.count(')')
	openn = s.count('(')
	close_q = len(s) // 2 - close
	open_q = len(s) // 2 - openn
	if not (open_q and close_q):
		return False
	j = 0
	for i in range(open_q):
		s[q_indexes[j]] = '('
		j += 1
	for i in range(close_q):
		s[q_indexes[j]] = ')'
		j += 1
	(s[q_indexes[open_q - 1]], s[q_indexes[open_q]]) = (s[q_indexes[open_q]], s[q_indexes[open_q - 1]])
	return psp(s)
t = int(input())
for j in range(t):
	s = input()
	s_list = [s[i] for i in range(len(s))]
	if not get_answer(s_list):
		print('YES')
	else:
		print('NO')


def Balance(s):
	b = 0
	for x in s:
		if x == ')':
			b -= 1
		if x == '(':
			b += 1
		if b < 0:
			return False
	return b == 0
n = int(input())
for _ in range(n):
	s = input()
	s = [x for x in s]
	left = len(s) // 2
	right = len(s) // 2
	index = []
	for x in range(len(s)):
		if s[x] == '(':
			left -= 1
		if s[x] == ')':
			right -= 1
		if s[x] == '?':
			index.append(x)
	for i in range(len(index)):
		if i < left:
			s[index[i]] = '('
		else:
			s[index[i]] = ')'
	p = True
	if left > 0 and right > 0:
		(s[index[left]], s[index[left - 1]]) = (s[index[left - 1]], s[index[left]])
		if Balance(''.join(s)):
			p = False
	if p:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	ss = list(s)
	(l, r, x) = (0, 0, 0)
	for i in s:
		if i == '(':
			l += 1
		elif i == ')':
			r += 1
		else:
			x += 1
	n = len(s)
	ln = n // 2 - l
	rn = n // 2 - r
	rnn = rn
	(lx, rx) = (0, 0)
	for i in range(n):
		if ss[i] == '?':
			if ln > 0:
				ss[i] = '('
				ln -= 1
				if ln == 0:
					lx = i
			else:
				if rn == n // 2 - r:
					rx = i
				rn -= 1
				ss[i] = ')'
	if n // 2 - l == 0 or n // 2 - r == 0:
		print('YES')
		continue
	(ss[lx], ss[rx]) = (ss[rx], ss[lx])
	ssss = ''.join(ss)
	bal = 0
	for i in ssss:
		if i == '(':
			bal += 1
		if i == ')':
			bal -= 1
		if bal < 0:
			print('YES')
			break
	if bal == 0:
		print('NO')
	elif bal > 0:
		print('YES')


from collections import Counter
t = int(input())
for _ in range(t):
	rbs = input().strip()
	c = Counter(rbs)
	n = sum(c.values()) // 2
	L = n - c['(']
	R = n - c[')']
	bal = 0
	if L == 0 or R == 0:
		print('YES')
		continue
	for i in range(2 * n):
		if bal < 0:
			break
		if rbs[i] == '?':
			L -= 1
			if L == 0:
				bal -= 1
				continue
			elif L == -1:
				bal += 1
				continue
		if rbs[i] == ')':
			bal -= 1
		elif rbs[i] == '(':
			bal += 1
		else:
			bal += -1 if L < 0 else 1
	else:
		print('NO')
		continue
	print('YES')


def helper(s):
	val = 0
	for i in s:
		if i == '(':
			val += 1
		elif i == ')':
			val -= 1
		if val < 0:
			return False
	return True
for caseno in range(int(input())):
	s = list(input().replace('()', '').strip())
	n = len(s)
	answer = 0
	if n % 2:
		print('NO')
		continue
	pval = n // 2
	nval = n // 2
	val = 0
	for ele in s:
		if ele == '(':
			pval -= 1
		elif ele == ')':
			nval -= 1
		else:
			val += 1
	if pval + nval != val:
		print('NO')
		continue
	s1 = []
	first_ind = -1
	last_ind = n
	for (j, i) in enumerate(s):
		if i == '?':
			if pval:
				first_ind = max(j, first_ind)
				s1 += ['(']
				pval -= 1
			elif nval:
				last_ind = min(j, last_ind)
				s1 += [')']
				nval -= 1
		else:
			s1 += [i]
	if helper(s1):
		if first_ind != -1 and last_ind != n:
			s2 = s1
			s2[first_ind] = ')'
			s2[last_ind] = '('
			if helper(s2):
				answer = 'NO'
			else:
				answer = 'YES'
		else:
			answer = 'YES'
	else:
		answer = 'NO'
	print(answer)


for i in range(int(input())):
	rbs = input()
	(bc, qmc, ss) = (0, 0, True)
	for i in range(len(rbs)):
		if rbs[i] == '(':
			bc += 1
		elif rbs[i] == ')':
			bc -= 1
		else:
			qmc += 1
		fl = len(rbs) - i - 1
		(lowest, highest) = (max((bc + qmc) % 2, bc - qmc), min(bc + qmc, fl - abs(fl % 2 - (bc + qmc) % 2)))
		if highest == lowest and qmc:
			if qmc != abs(highest - bc):
				ss = False
			qmc = 0
			bc = highest
	print(['NO', 'YES'][ss])


from copy import deepcopy

def solve():
	a = list(input())
	cop = deepcopy(a)
	mas = [0] * (len(a) + 1)
	our = []
	openn = a.count('(')
	close = a.count(')')
	ask = a.count('?')
	for i in range(len(a)):
		if a[i] == '?':
			if len(a) // 2 >= openn + 1:
				a[i] = '('
				openn += 1
			else:
				a[i] = ')'
				close += 1
	for i in range(len(a)):
		if a[i] == ')':
			mas[i + 1] = mas[i] - 1
		elif a[i] == '(':
			mas[i + 1] = mas[i] + 1
	del mas[0]
	minn = 0
	for i in range(len(a) - 1, 0, -1):
		if a[i] == ')' and cop[i] == '?':
			minn = mas[i - 1]
		else:
			minn = min(minn, mas[i])
		if a[i] == '(' and cop[i] == '?':
			if minn > 1:
				print('NO')
				return 0
	print('YES')
nnnn = int(input())
while nnnn:
	nnnn -= 1
	solve()