트리

이진 트리(binary tree)는 매우 중요한 기본 자료 구조이다. 이진 트리의 모든 노드는 최대 두 개의 자식 노드를 가질 수 있고, 두 자식에는 순서가 있어 왼쪽 자식이 오른쪽 자식보다 먼저이다. 노드가 $n$개인 이진 트리를 $BT$라고 하자. $BT$의 노드에는 $1$부터 $n$까지 서로 다른 번호가 매겨져 있다. 자식이 하나도 없는 노드를 리프 노드(leaf node)라고 부른다.

이진 트리의 모든 노드를 방문하는 순회 방법에는 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)의 세 가지가 있다. 노드 $v$의 왼쪽 자식을 $v.\text{left}$, 오른쪽 자식을 $v.\text{right}$라 하고, 자식이 없으면 그 값은 비어 있다($\varnothing$)고 하자. 세 순회는 다음과 같이 재귀적으로 정의된다.

• 전위 순회: 현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리와 오른쪽 서브트리를 차례로 순회한다.
• 중위 순회: 왼쪽 서브트리를 순회한 뒤 현재 노드를 방문하고, 이어서 오른쪽 서브트리를 순회한다.
• 후위 순회: 왼쪽 서브트리와 오른쪽 서브트리를 차례로 순회한 뒤, 마지막에 현재 노드를 방문한다.

어떤 이진 트리 $BT$를 전위 순회한 결과와 중위 순회한 결과가 주어진다. 이 두 순회 결과를 이용하면 원래의 이진 트리를 유일하게 복원할 수 있다. 같은 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 $n$이 주어진다 ($1 \le n \le 1{,}000$). 이진 트리의 모든 노드에는 $1$부터 $n$까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 트리를 전위 순회한 결과가, 그 다음 줄에는 중위 순회한 결과가 공백으로 구분되어 주어진다. 입력으로는 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 주어진다.

각 테스트 케이스마다 해당 트리를 후위 순회한 결과를 한 줄에 공백으로 구분하여 출력한다.