请注意,内存限制是非标准的。
最近 Arthur 和 Sasha 研究了正确的括号序列。 Arthur 完全理解这个主题,并且对正确的括号序列感到非常惊讶,因此他甚至为自己找到了一个最喜欢的长度为 2n 的正确括号序列。与亚瑟不同,萨莎对这个话题的理解非常糟糕,并且打破了亚瑟最喜欢的正确括号顺序只是为了惹恼他。
亚瑟只记得他最喜欢的序列是每个左括号 ('(') 到相应右括号 (')' 的大致距离。对于第 i 个左括号,他记住了段 [li, ri],其中包含到相应右括号的距离。
形式上来说,对于第i个左括号(按从左到右的顺序)我们知道它的位置与对应的右括号的位置之差属于段[li,ri]。
帮助亚瑟恢复他最喜欢的正确括号序列!
输入
第一行包含整数 n (1 ≤ n ≤ 600),即 Arthur 最喜欢的正确括号序列中左括号的数量。
接下来的 n 行包含数字 li 和 ri (1 ≤ li ≤ ri < 2n),表示距第 i 个左括号和相应右括号的距离的段。
如果我们从左到右列出片段,则片段的描述按照 Arthur 最喜欢的序列中左括号出现的顺序给出。
输出
如果可以通过给定数据恢复正确的括号序列,则打印任何可能的选择。
如果 Arthur 出错,并且没有与给定信息相对应的序列,则打印一行“IMPOSSIBLE”(不带引号)。
示例
输入 #1
4 1 1 1 1 1 1 1 1
输出 #1
()()()()
输入 #2
3 5 5 3 3 1 1
输出 #2
((()))
输入 #3
3 5 5 3 3 2 2
输出 #3
IMPOSSIBLE
输入#4
3 2 3 1 4 1 4
输出#4
(())()