Binary Search Heap Construction

In this problem a heap is a tree whose nodes are each assigned a priority (a number) such that the priority of every node is less than the priority of its parent. As a consequence, the root holds the greatest priority in the whole tree — one of the reasons heaps are used to implement priority queues and to sort.

A binary tree in which every node has both a label and a priority, and which is at the same time a binary search tree with respect to the labels (each node's label is greater than every label in its left subtree and smaller than every label in its right subtree) and a heap with respect to the priorities, is called a treap.

Given a set of label/priority pairs with pairwise-distinct labels and pairwise-distinct priorities, construct the treap that contains this data. Because the labels and the priorities are all distinct, this treap is unique.

The input contains several test cases. Every test case starts with an integer $n$ ($1 \le n \le 50000$). Then follow $n$ pairs $l_1/p_1, \dots, l_n/p_n$ giving the label and priority of each node. Every label is a non-empty string of lower-case letters and every priority is a non-negative integer; within one test case all labels are distinct and all priorities are distinct. The last test case is followed by a single $0$, which is not processed.

For each test case, output on a single line the treap that contains the specified nodes. A treap is printed as (<left-sub-treap><label>/<priority><right-sub-treap>). The sub-treaps are printed recursively in the same way, and an empty sub-treap is omitted.