|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||24||14||14||70.000%|
Dave loves strings consisting only of ‘(’ and ‘)’. Especially, he is interested in balanced strings. Any balanced strings can be constructed using the following rules:
Dave has a string consisting only of ‘(’ and ‘)’. It satisfies the followings:
Your task is to compute Dave’s string. If there are multiple candidates, output the minimum in lexicographic order. As is the case with ASCII, ‘(’ is less than ‘)’.
The input consists of a single test case, which contains an integer A (1 ≤ A ≤ 109).
Output Dave’s string in one line. If there are multiple candidates, output the minimum in lexicographic order.
Sample 1: There are infinitely many strings which can be balanced by only one swap. Dave’s string is the shortest of them
Sample 2: String “))(()(” can be balanced by 4 swaps, but the output should be “)())((” because it is the minimum in lexicographic order.