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