def p(s):
 r=[]
 while s and(S:=s[0])!=')':
  if S.isalpha():r+=S,
  if'('==S:r+=(K:=p(s[1:]))[0],;s=K[1]
  s=s[1:]
 return r,s
F=lambda x:(O:=ord(str(x)[0]))<92and(64<O<91or all(F(i)for i in x[-2:]))
R=lambda x:[i for i in x if i]
def f(s,l=0,r=0):
 if F(s):
  J=[]
  while s:S=s.pop(0);J+=[[S,s.pop(0)]if~-len(s)>0==F(s[0])else S]
  c=[f([*J[0]])]if(t:=F(J[0])==0)else[];s=J[t:];c+=[f(R([l,s[0],r]))]if(S:=sum(map(F,s))%2)else[];s=s[S:]
  while s:
   if F(s[0]):a,b=s[:2];c+=a,f(R([l,b,r]))if F(b)else f(b),;s=s[2:]
   else:c+=s[0],;s=s[1:]
  return f(c)
 c=[]
 while s:c+=[f(j,c and 0==F(c[-1])and c.pop(),r=f(s))]if F(j:=s.pop(0))and list==type(j)else[j]
 return c
P=lambda e,l=0:e if str==type(e)else'('*(Y:=l>=1<len(e))+''.join(P(i,l+1)for i in e)+')'*Y
M=lambda s:P(f(p(s)[0]))
 
print(M('x F G y'))
print(M('F x G y'))
print(M('x F y G z'))
print(M('(F x) G H y'))
print(M('(F G H) x'))
print(M('(u G H) x'))
print(M('(G H) x'))
print(M('x (F G H) y'))
print(M('x (u G H) y'))
print(M('x (G H) y'))
print(M('x ((D a) F G (u H J) K) y'))
print(M('x(XY)y'))
print(M('uKKKv'))
print(M('U(xVW)yZa'))
print(M('MnP(QRsTU)VWx'))
print(M('x(XXxYYYdDD)y'))
print(M('a((DEF)GHJ)Kb'))
print(M('c((k(PQRSTU)m)(VW)(XY)(ZA)BCD)n'))
 

ZGVmIHAocyk6CiByPVtdCiB3aGlsZSBzIGFuZChTOj1zWzBdKSE9JyknOgogIGlmIFMuaXNhbHBoYSgpOnIrPVMsCiAgaWYnKCc9PVM6cis9KEs6PXAoc1sxOl0pKVswXSw7cz1LWzFdCiAgcz1zWzE6XQogcmV0dXJuIHIscwpGPWxhbWJkYSB4OihPOj1vcmQoc3RyKHgpWzBdKSk8OTJhbmQoNjQ8Tzw5MW9yIGFsbChGKGkpZm9yIGkgaW4geFstMjpdKSkKUj1sYW1iZGEgeDpbaSBmb3IgaSBpbiB4IGlmIGldCmRlZiBmKHMsbD0wLHI9MCk6CiBpZiBGKHMpOgogIEo9W10KICB3aGlsZSBzOlM9cy5wb3AoMCk7Sis9W1tTLHMucG9wKDApXWlmfi1sZW4ocyk+MD09RihzWzBdKWVsc2UgU10KICBjPVtmKFsqSlswXV0pXWlmKHQ6PUYoSlswXSk9PTApZWxzZVtdO3M9Slt0Ol07Yys9W2YoUihbbCxzWzBdLHJdKSldaWYoUzo9c3VtKG1hcChGLHMpKSUyKWVsc2VbXTtzPXNbUzpdCiAgd2hpbGUgczoKICAgaWYgRihzWzBdKTphLGI9c1s6Ml07Yys9YSxmKFIoW2wsYixyXSkpaWYgRihiKWVsc2UgZihiKSw7cz1zWzI6XQogICBlbHNlOmMrPXNbMF0sO3M9c1sxOl0KICByZXR1cm4gZihjKQogYz1bXQogd2hpbGUgczpjKz1bZihqLGMgYW5kIDA9PUYoY1stMV0pYW5kIGMucG9wKCkscj1mKHMpKV1pZiBGKGo6PXMucG9wKDApKWFuZCBsaXN0PT10eXBlKGopZWxzZVtqXQogcmV0dXJuIGMKUD1sYW1iZGEgZSxsPTA6ZSBpZiBzdHI9PXR5cGUoZSllbHNlJygnKihZOj1sPj0xPGxlbihlKSkrJycuam9pbihQKGksbCsxKWZvciBpIGluIGUpKycpJypZCk09bGFtYmRhIHM6UChmKHAocylbMF0pKQoKcHJpbnQoTSgneCBGIEcgeScpKQpwcmludChNKCdGIHggRyB5JykpCnByaW50KE0oJ3ggRiB5IEcgeicpKQpwcmludChNKCcoRiB4KSBHIEggeScpKQpwcmludChNKCcoRiBHIEgpIHgnKSkKcHJpbnQoTSgnKHUgRyBIKSB4JykpCnByaW50KE0oJyhHIEgpIHgnKSkKcHJpbnQoTSgneCAoRiBHIEgpIHknKSkKcHJpbnQoTSgneCAodSBHIEgpIHknKSkKcHJpbnQoTSgneCAoRyBIKSB5JykpCnByaW50KE0oJ3ggKChEIGEpIEYgRyAodSBIIEopIEspIHknKSkKcHJpbnQoTSgneChYWSl5JykpCnByaW50KE0oJ3VLS0t2JykpCnByaW50KE0oJ1UoeFZXKXlaYScpKQpwcmludChNKCdNblAoUVJzVFUpVld4JykpCnByaW50KE0oJ3goWFh4WVlZZEREKXknKSkKcHJpbnQoTSgnYSgoREVGKUdISilLYicpKQpwcmludChNKCdjKChrKFBRUlNUVSltKShWVykoWFkpKFpBKUJDRCluJykpCg==