10000
((())((()(()))()(())())((((()()(((())(())((())()((((()))())))))(()((((((((())))()))(())))((()(()(())))))(((())()()(((()(((((((((()))))))))(())))((()))()((())())(((((()))))()))(())(((((()((())))((())(()(((())))))(())))))))((()(())))())((((((()))(()()(((()))(((()))()()(()((())))))))((((((()))(())(((()))((((())))))))()(()))(()((((())))())))()(((()((())))())()))((((())))))()()((())((()())((()))))(((((())()))(()))(((())))))))(((())))()()(((()())(((())(()))()((())(()))))(((())))())((())))(()(()()())((((((())))(((()))()()))((()(())))))())((((()()()))))()(()((())())))(((((())()()))()(()())(()()(((()))(()()))))()()((())((((((())))())))((())))(((()((((())))())(((((())((())())))())(())()((()(((((()))))()))(()))))(((())(()((((())))))))())(((())(()(()((())))))()((((())))((((())))((((()(()())((())(()()(()(((())))))))(()(())))(((((((()()((((()))))))()))(())((())))))(()()()))))))))(((((()))))((()))())(())()(((()))(()(()())(()(()))))))(((()(()))()))()(((())(((())((())))((()((())))))(()((((())))((()))(()))))(()()((()(()))()))(((()))(((()()))((((((())(()))))())(())())))))((((((()(())))()(()((()))))((())))()(((())))(((()((()())((())()((()))))))))()(((()))(((()((())))())))(((()())(((((((()))))(())))))((()()(()(())(()))((((((())))(()(((((())))(()))(())))(((((())())((())))()((((()))))))(((()(()(()()))((((()(()))())))))()()()(()())(((()((()()))))(()(((())))((()(((((()))())(()(((()()))))())))))((((())))()())(()))))((((((()))))(((()))()(())())()((()((((())(())))()))))(())))(((())(((()()))())()((((()))))))))((()))((()())()((()))((())(((())(((())(((())()((((())))))(()((())))((())(((())))))())))()))))((())))(((((((((()())))()(((()())((((())))()))()(((())))))((())))()((())((()))))(((())))(())(())(())(())(()((()(((((())()())((((()))))))(())))()(())(()(()(((()))())))))(((())((()))()(((((()))))))((((()()(())())()((()((((())()()))(()))()((()())))(())))())()((())))))(())((((())()))()))(((((()))))((((((()))(()(((()))))()(()))(()))(((()))()))((((()))))()))(((())(()((()))))())((((((())(()(((())))))(()))(()))((())))(())()()()((()()(((((())(())))())(())))(()(((((()(((())())))(((())(()()(())((())(()((()(())))))))))(()))(()))()(((()))())(((()))))())())))((((((((()()(((())))))(())))(()))(()))()((((((())))((()((()())))((()((())))))(((())))((((((())((())()))())()(((((())(((((((()))))())())))(()(())))(()(((((()))))))(((()))))((((()))))))(()))((()))()(())))(()()))(((())))(((((((())))()))())(())))((((()(()())))()(((((((((()))(())))())(()()((()(())(())))))((((())))))(((((()))(((()())())))()))(()))(())(((())))))(())))((((((()((())()))))()()(((()))(())()))()))((()))(((((((((())))())))(((()))))()((((())))))(((())))))(((((((())))((((((()))))))()((((((((((((())))())))))((()))))()()((())(()()()()(())))))(((())((((())(()))((()((()))(())(((((()(())))()))(())))(((((())))())()))((()))((()))())()(()(((())))))((()(()(()((())))()())((((()())((()((())))(()))(()))()(()(())))((((()))())))((((((((()))))(()))(()))()()(((()((((())))())))()(((((()()))))))(((((((((())(())())()((())))())(())(()))(((())(()))))()((())((()))))(((()))())((((()))))((()()((((())))((((()))))))((()))()))(((()))(()))((())((((())(((())(()))))((())(()(()(((()))))))()(())(()((()()))(((((((()())))()(()))())())((())))))(((())(())))(((((())))))()((()(((((()))))))(((((())))))))(()))))(())(((())))()(((((((()))))(())(()))()))(((()(()((()()(((())(()))())))))))))(()()))(((()(((())))(()((()()))(((()((())(()))((((()))())()))())(())(((((()))(((())(())(((((((()))))()((((())))))((()))()))(()))(()((())(())))))()(((()()))()))()(()((())((()))))((((()))))))))(((()()))(())())(((((((((())))(()()))((())))())((()))))((()())))(((((((()(((())))))((((())(())())(())(((()(((((()))()))(()()()))))()))(((())(((()())())())))()(((()))(()((()()))(())((((())()())())())))))()(((((())()()))())((()))))(()(((()())))))((()()))(((()))())((()))(()()((((()(()(()))(((((()))))))(())(((((()))))(())))(((()))((()())())))(()))))((((()))())()(((((()()))(((())))))()))(((())))(((((((((())))()))(((()))()))())(()((((((()))()((((()))))))()(()))((())))(()(()))(((((())))(((((()))(()()(()()((((())()))()))))(((())))())()((())(((()))))(((((())))()))))((())))))(()((((()))())))((())(())(()(())((())((()))))())())))((((())))(()((())))((((()))))((())))((((((((())))))(((()))()))((()((())(((()))((((())))(((()))(()(((((()))))()(((((()())())))))))))))()((()))())((()))((())(((()))))((())))(((())()((())))))))(()((()())(()))(((((())((()))))())((()((((())))(((())))))())()(()))((((())()((()(())))((((())(((((()(((())))))))(())))()(()(())()))(())()()))()()()(()))(((((()()))())))()()))((())(((()((()))(()(((((())))))(())))((((())))))()))((()()))(((((((((())))()))(()))(()))()((())(())))())(((((()(()))((())())((((())))()(((())))(((((((()))((((())))))()()))(()))((()(())))())))(((()((((()())))((((()))))()))((((())()))())((((()(((()))))(((((()())())(((())))))(((()())))(())((((((())))())(()()(((()))))())(())((()((())())))(()(((())(((((()))))(())((())))))))))(((()((()))))(())(((())))))(()(((()))((())(((()))))))(()())))()))((((()(((()))()((((((()))())(()((()))(()))))((())()))))()((((()))))()((()(((()((()))))))((())())(((()()(())))(())((()))(((((()))))))(((((()()())())(()()))()(((()()))()))(((())()))))((((((((((()((((((())))))())))()))((())()()))()((((((((()))))(((((((()))))()()(((()))))(((()))))(())))())()()((((((((()()))))(()))(()((((((()(()))())(()))))(()())()()()(((())(()(()(())())))))))()((()))((((()(()))()))))))(())))(()())())((((())))(((())((())((((((()))))))))(()(())))))((((())())()(((()(((())))))))(())())((()))(()((()))((()())((()())(()((()(((()))))()))((((())))))))())(((((())))()()(((((((((())((()(()(((()))))(()()))))(()))(())((()))())(()()))()(((()))(())))((()))((())(((())(()(()))))))()(((((())))))()((())))((())())((((())))(((((((())())))()))(())()))))()(()()()))()(((())(())))))((()((((())))(((()))())))((())))(((((()))))))()(())(())()()((((()))))((((()))((()(()))()))(()))))((()((()()(((()()))()()))())))((()))()()((()(())(()))()()(((((())()(((()))))(())(()((((())))())))((())))(((((()))))())()))((((((())((())(((())))))))())()(((((()(((((()))()()((()()))))))()((()(((()))((()()((()(()))(())))))(()(()((()(((()))()))))()))()()((((((()))))())()))(()((()(()((())))))((()())(((())()))()(((()))()()))))((((()(((()))))))(((()((())))))(()(()))(()))()(()())))((()))(()))((()(())((()()(())))(())(()(())))((())((()))))))))(((((())))((()()(()))()((((()))))(()(((())()))((((())))((((((()))))(((())))()((())(((()())(())))))()))))((((((((()))(())((((()()))())((()(())))))((())((()))))(()))(()((((()))(())))(())()())((())))((()))(())()(()((()))((())((())(())(()())((()((())))()(((()))))))))((()))(()(((((((()(()))))((()((()())()(((()(()))()))))(((())((()())())))))((()))(())((()))))()(((())((()(((()))))))(()))))((())(()((((((()())))())))(()((((()))))))(((((())))(()))(((()(((()())))((((()))))((((()((((()))))()))()(((())(((((()()))))())())((((())))(()((((()))))((((())(()))))))))(((())))))((())))(()(()))())((((())))()(((()(()()((())))((((()))()))))(()(()((((()))))(()())))()))((())())(())(((())))))))(((())((()(()))((((()(((()))())))(()))))())(()((())))((((((((()))())())()())))(())((((((()))(())))()))((()()(((())()()())))()((((()(()()((())(())(())())))()()((())))((()(()))())((()((((((())()))()(())))((())()(((()((()))))()))))())))((())))))((())))()(((())))((((()))(((()()))))((((())))))((((()()((()()))(((()))(((()))))))(()((()))))(((()))()((()))(((((((())))(((()))))(((((()))((())(((((()))))()())(((()))(()())()())))(()))(())()))((((()))))((())()))())))((((()())(()((())(()((((()()))))))))())((()))()()(()(((((())(()))()(((((()))(()()()())()())()()((((())))))))))(()))))((())(((())(((())())((())))))((((((()))(())(())(((()(()))(()((())())((()())))()(((())))))((((())))))((()((()))))()(()()))()())((((((()))))))))(((((((()))())(()())(((())(())))))((()))()(((()(((()))))((()())))()((((())((())()()((((((((())))))()))()))))(()()))(()((((())))))))()((()))(((((((()))))()((())))(()))()(())))()((((()))((())(())))))(())(((()((())((()))))(())(())(((((()((())))()))((((()())))()))()(((())((((((())))())(()))((())))(((((()))())((()())))()))((())(((())))))))(())((((())(())))()(()))(((()()))))(()(())((((((((())))))(())(((())((()(((((((()))))))(())((((()))))))))())))((()))))(((((()((()(()((())())))(((()))))(((((()()))())()((((()()((()(()))))(())((()))))(())()))(((())(())(((((((((())((()((((())))()))))(()())())(()())((()(()((())((())))(()))))((()((())))((((()))(((()))()))(()(()(()((())))))(()(())((((()(()))((())()))()))))))(()))((()((((())))))))())(()(()(()))))))((()((()((())(((((()(((())()))))())((())))))))()())(()()(()()(()(()(()))))))()(())(((()((((()))))(((())(()))()))(((((((((())())())())((())))(((())((()))))))(())((())((()))))((()))(((((())))())))((((())))))))))((()()))())(((())))((()())((()())()((((()))((())))(()(((()))))(((())))(()()(((()()))))()))))((((()(((()))()))()((())))()((()((())))()((())(((()(()))())(((())))))))())(()))()((()())((())))((())()))((((((())((((()(()(((((()))))()))))())((()))()))(())())()(((()(()))((())((())())))((((((())))))()))(()(((())))(((()((())(((())))))(()))((()())))((((((()))))((((()((())))(((()))(((())))))(((((()((((()))()())(())))(()))(((((((())())))((((())))()(())((()(((()()))))()(((()(())())())())((())))))()))))(((()))(()))))((())(((((()())))(((())())))(()())()((((()()))())(((((()())(((((()))))()()))(())(()((((())))(((())))(((())))))(()))(()))(())))))(())((((()))))))(())((()())(((())))))))()()(((()((((())))((()))))((((((((())))))(())(((()))()))(()()))((((()))))))((()))(((()())))))(()())()((((()))((((((()(())(((()))()((((((())))))(()))))()(()))(((())(())(())(((((())))()))))))())((()))(((((((()))))()))))((((((())))(()((())(())(((((()))))(())))))((((()(())(()))))))()((())())(((())(((()(((()))))()))(((())(((())))((()(())()((((((()())))())())()))(()(())))))(((()(()()(()((()(()))()))())))()())((((())(((()((())()(()))))(()))))(((())))))((((()))((((())())(((()((())((((((())()))))(()))))())))()()))((()))(((()))((((()))))()(((((((()))(()())))(())((()))))())))(((()((())))))())))((((()((((())))(((()((()((((((())))))()))))((())())())())))((())))((()))((((((())))())((())))())((())))((((()))))((()(((())))))())()()())))
