미사와 씨의 뿌리 있는 이진 트리

당신은 친한 친구인 미사와 씨의 생일이 가까워진 것을 알아차리고, 뿌리 있는 이진 트리를 선물하기로 했다. 여기서 뿌리 있는 이진 트리란 다음과 같은 그래프 구조이다. (그림 1)

• 각 정점에는 그 정점의 부모라 불리는 정점이 정확히 하나 존재하며, 부모와 간선으로 연결되어 있다. 다만 루트라 불리는 하나의 정점만 예외적으로 부모를 갖지 않는다.
• 각 정점은 왼쪽 자식이라 불리는 정점을 정확히 하나 갖거나, 갖지 않는다. 왼쪽 자식을 갖는 경우, 왼쪽 자식과 간선으로 연결되어 있으며, 왼쪽 자식의 부모는 그 정점이다.
• 각 정점은 오른쪽 자식이라 불리는 정점을 정확히 하나 갖거나, 갖지 않는다. 오른쪽 자식을 갖는 경우, 오른쪽 자식과 간선으로 연결되어 있으며, 오른쪽 자식의 부모는 그 정점이다.

그림 1. 두 뿌리 있는 이진 트리와 그 합성의 예

당신은 손수 만든 물건을 선물하고 싶었기 때문에, 시판 중인 뿌리 있는 이진 트리 두 개를 사서 겹쳐 합성함으로써 더 나은 뿌리 있는 이진 트리 하나를 만들기로 했다. 당신이 사 온 두 트리의 각 정점에는 음이 아닌 정수가 적혀 있다. 미사와 씨는 정점 수가 적으면서 각 수치가 큰, 가성비가 좋은 트리를 좋아하므로, 다음 절차에 따라 새로운 이진 트리를 만들기로 한다.

1. 두 이진 트리 각각의 루트에 적힌 정수의 합을 새로운 이진 트리의 루트에 적을 정수로 한다.
2. 두 이진 트리의 루트가 모두 왼쪽 자식을 갖는 경우, 그것들을 루트로 하는 이진 트리 각각을 합성한 이진 트리를 만들어 새로운 이진 트리의 루트의 왼쪽 자식으로 한다. 그렇지 않은 경우, 새로운 이진 트리의 루트는 왼쪽 자식을 갖지 않는다.
3. 두 이진 트리의 루트가 모두 오른쪽 자식을 갖는 경우, 그것들을 루트로 하는 이진 트리 각각을 합성한 이진 트리를 만들어 새로운 이진 트리의 루트의 오른쪽 자식으로 한다. 그렇지 않은 경우, 새로운 이진 트리의 루트는 오른쪽 자식을 갖지 않는다.

당신은 실제로 합성하는 작업을 하기 전에, 완성될 뿌리 있는 이진 트리가 어떻게 되는지 확인하기로 했다. 사 온 두 뿌리 있는 이진 트리의 정보가 주어지므로, 위 절차에 따라 합성되는 새로운 뿌리 있는 이진 트리를 구하는 프로그램을 작성하시오.

여기서 뿌리 있는 이진 트리의 정보는 다음과 같은 형식의 문자열로 표현한다.

(왼쪽 자식을 나타내는 문자열)[루트에 적힌 정수]\(오른쪽 자식을 나타내는 문자열)

정점이 존재하지 않는 트리는 빈 문자열로 한다. 예를 들어 그림 1에서 합성되어 만들어진 새로운 뿌리 있는 이진 트리는 (()[6]())[8](((()[4]())[7]())[9]())처럼 쓴다.

입력은 다음 형식으로 주어진다.

$A$

$B$

$A$, $B$는 각각 사 온 뿌리 있는 이진 트리의 정보를 나타내는 문자열이며, 길이는 $7$ 이상 $1000$ 이하이다. 주어지는 정보는 앞서 설명한 형식을 따르며, 불필요한 공백 문자 등을 포함하지 않는다. 또한 정점이 존재하지 않는 뿌리 있는 트리는 입력으로 주어지지 않는다. 각 정점에 적힌 정수는 $0$ 이상 $1000$ 이하라고 가정해도 좋다. 다만 출력의 각 정점에 적히는 정수는 이 범위를 벗어날 수도 있다는 점에 주의하시오.

두 뿌리 있는 이진 트리를 합성하여 완성되는 새로운 뿌리 있는 이진 트리의 정보를 한 줄로 출력하시오. 특히, 행 끝의 개행을 제외하고 불필요한 공백 문자 등을 포함하지 않도록 주의하시오.