描述

关于树的定义请阅读问题G的描述。以下我们定义堆的基本术语。堆是一棵每个内部节点都分配了优先级（一个数字）的树，且每个内部节点的优先级都小于其父节点的优先级。因此，根节点具有树中的最大优先级，这也是堆可用于实现优先队列和排序的原因之一。

若一棵二叉树的每个内部节点同时具有标签和优先级，并且对于标签而言是二叉搜索树，对于优先级而言是堆，则称其为树堆（treap）。你的任务是，给定一组标签-优先级对（标签和优先级均唯一），构造包含这些数据的树堆。

输入

输入包含多个测试用例。每个测试用例以整数$n$开始，其中$1 \leq n \leq 50000$。接下来是$n$对字符串和数字$l_1/p_1, \dots, l_n/p_n$，表示每个节点的标签和优先级。字符串非空且由小写字母组成，数字为非负整数。最后一个测试用例后跟一个$0$。

输出

对于每个测试用例，输出一行表示树堆的内容。树堆按如下格式打印：(<左子树堆><标签>/<优先级><右子树堆>)。子树递归打印，若为叶子节点则省略子树部分。

输入数据示例

7 a/7 b/6 c/5 d/4 e/3 f/2 g/1
7 a/1 b/2 c/3 d/4 e/5 f/6 g/7
7 a/3 b/6 c/4 d/7 e/2 f/5 g/1
0

输出数据示例

(a/7(b/6(c/5(d/4(e/3(f/2(g/1)))))))
(((((((a/1)b/2)c/3)d/4)e/5)f/6)g/7)
(((a/3)b/6(c/4))d/7((e/2)f/5(g/1)))

来源

Ulm Local 2004