이진 검색 트리

이진 검색 트리는 다음 세 조건을 모두 만족하는 이진 트리이다.

• 어떤 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 그 노드의 키보다 작다.
• 어떤 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 그 노드의 키보다 크다.
• 왼쪽 서브트리와 오른쪽 서브트리도 각각 이진 검색 트리이다.

전위 순회(루트 → 왼쪽 → 오른쪽)는 루트를 먼저 방문한 뒤 왼쪽 서브트리, 오른쪽 서브트리를 차례로 방문하면서 각 노드의 키를 출력한다. 후위 순회(왼쪽 → 오른쪽 → 루트)는 왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문한 뒤 마지막에 루트의 키를 출력한다.

어떤 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 같은 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

트리를 전위 순회한 결과가 한 줄에 하나씩 주어진다. 각 노드의 키는 $10^6$보다 작은 양의 정수이며, 노드의 개수는 최대 10,000개이다. 키가 같은 노드는 존재하지 않는다.

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.