{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch2\u003e\u003c/h2\u003e\n\n\u003cp\u003e\nDave loves strings consisting only of \u0027(\u0027 and \u0027)\u0027. Especially, he is interested in balanced strings. Any balanced strings can be constructed using the following rules:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e A string \"()\" is balanced.\u003c/li\u003e\n\u003cli\u003e Concatenation of two balanced strings are balanced.\u003c/li\u003e\n\u003cli\u003e If $T$ is a balanced string, concatenation of \u0027(\u0027, $T$, and \u0027)\u0027 in this order is balanced. For example, \"()()\" and \"(()())\" are balanced strings. \")(\" and \")()(()\" are not balanced strings.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nDave has a string consisting only of \u0027(\u0027 and \u0027)\u0027. It satis\u0026#xc;es the followings:\n\u003c/p\u003e\n\n\u003cul\u003e\n\u003cli\u003e You can make it balanced by swapping adjacent characters exactly $A$ times. \u003c/li\u003e\n\u003cli\u003e For any non-negative integer $B$ ($B \u0026lt; A$), you cannot make it balanced by $B$ swaps of adjacent characters.\u003c/li\u003e\n\u003cli\u003e It is the shortest of all strings satisfying the above conditions.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e\nYour task is to compute Dave\u0027s string. If there are multiple candidates, output the minimum in lexicographic order. As is the case with ASCII, \u0027(\u0027 is less than \u0027)\u0027.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\nThe input consists of a single test case, which contains an integer $A$ ($1 \\leq A \\leq 10^9$).\n\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\nOutput Dave\u0027s string in one line. If there are multiple candidates, output the minimum in lexicographic order.\n\u003c/p\u003e\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e)(\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003e\nThere are infinitely many strings which can be balanced by only one swap. Dave\u0027s string is the shortest of them.\n\u003c/p\u003e\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e)())((\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003e\nString \"))(()(\" can be balanced by 4 swaps, but the output should be \")())((\" because it is the minimum in lexicographic order.\n\u003c/p\u003e\n\n"}}]}