bobo found an ancient string. The string contains only three charaters -- "(", ")" and "?".
bobo would like to replace each "?" with "(" or ")" so that the string is valid (defined as follows). Check if the way of replacement can be uniquely determined.
Note:
An empty string is valid.
If S is valid, (S) is valid.
If U,V are valid, UV is valid.