Parenthese sequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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.

Input

The input consists of several tests. For each tests:

A string s1s2…sn (1≤n≤106).

Output

For each tests:

If there is unique valid string, print "Unique". If there are no valid strings at all, print "None". Otherwise, print "Many".

Sample Input

?? ???? (??

Sample Output

Unique Many None

Hint

Source

2014 Multi-University Training Contest 5

提交代码