← 返回题目列表

Codeforces · 508/E

E. 亚瑟和括号

中文机器翻译题面 查看原题

请注意,内存限制是非标准的。

最近 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

(())()