트립(이진 탐색 힙) 구성

힙(heap) 은 각 노드에 우선순위(priority)(숫자)가 매겨진 트리로, 모든 노드의 우선순위가 그 부모 노드의 우선순위보다 작은 트리를 말한다. 따라서 루트가 트리 전체에서 가장 큰 우선순위를 가지며, 이 성질 덕분에 힙은 우선순위 큐를 구현하거나 정렬을 수행하는 데 쓰인다.

각 노드가 레이블(label) 과 우선순위 를 함께 가지며, 레이블에 대해서는 이진 탐색 트리(모든 노드의 레이블이 그 왼쪽 서브트리에 있는 모든 레이블보다 크고 오른쪽 서브트리에 있는 모든 레이블보다 작음)이면서, 동시에 우선순위에 대해서는 힙 인 이진 트리를 트립(treap) 이라고 한다.

레이블이 서로 다르고 우선순위도 서로 다른 레이블/우선순위 쌍들의 집합이 주어질 때, 이 자료를 담는 트립을 구성하여라. 레이블과 우선순위가 모두 서로 다르므로 이러한 트립은 유일하다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ ($1 \le n \le 50000$) 으로 시작한다. 이어서 각 노드의 레이블과 우선순위를 나타내는 $n$ 개의 쌍 $l_1/p_1, \dots, l_n/p_n$ 이 주어진다. 각 레이블은 비어 있지 않은 소문자 문자열이고, 각 우선순위는 음이 아닌 정수이다. 한 테스트 케이스 안에서 모든 레이블은 서로 다르고 모든 우선순위도 서로 다르다. 마지막 테스트 케이스 다음에는 $0$ 하나가 주어지며, 이 값은 처리하지 않는다.

각 테스트 케이스마다, 주어진 노드들을 담는 트립을 한 줄에 출력한다. 트립은 (<왼쪽 서브트립><레이블>/<우선순위><오른쪽 서브트립>) 형태로 출력한다. 서브트립은 재귀적으로 같은 방식으로 출력하며, 비어 있는 서브트립은 생략한다.