난독화된 트리

어떤 자료 전송 부서는 숫자로 이루어진 트리를 사무실 사이에서 몰래 주고받아야 한다. 전송 내용을 암호화하기는 하지만, 그것만으로는 부족하다고 보고 암호화 전에 트리를 한 번 뒤섞기로 했다.

트리는 텍스트로 늘어놓는다. 뒤섞기는 노드마다 자식 트리를 늘어놓는 순서를 전위, 중위, 후위 중에서 무작위로 골라 적용하는 방식이다. 세 순서의 뜻은 다음과 같다.

• 전위: 노드의 값을 먼저 적고, 그 뒤에 자식 트리를 왼쪽부터 차례로 적는다.
• 중위: 첫째 자식 트리, 노드의 값, 둘째 자식 트리 순으로 적는다.
• 후위: 자식 트리를 왼쪽부터 차례로 적고, 마지막에 노드의 값을 적는다.

자식 트리는 어느 순서를 쓰더라도 항상 왼쪽에서 오른쪽으로 적는다.

예를 들어 아래 그림의 트리를 보자. 루트의 값은 5이고 자식 트리가 셋이다. 첫째 자식 트리의 루트는 값이 7이고 자식이 하나인데, 그 자식은 값이 1이며 잎 2와 잎 8을 자식으로 둔다. 둘째 자식 트리의 루트는 값이 3이고 잎 8과 잎 9를 자식으로 둔다. 셋째 자식 트리는 잎 2 하나다.

루트에 전위, 값이 7인 노드와 값이 1인 노드에 후위, 값이 3인 노드에 중위를 적용하면 노드 값이 다음 순서로 나온다.

5 2 8 1 7 8 3 9 2

이 형태만으로는 원래 트리를 되살릴 수 없다. 그래서 정보를 덧붙인다. 잎이 아닌 노드의 출력 앞에는 수가 하나 또는 둘 붙는다. 먼저 어떤 순서를 썼는지 알리는 음수가 온다.

• -1은 전위
• -2는 중위
• -3은 후위

전위나 후위면 그 음수 뒤에 자식 트리의 개수를 적은 양수가 하나 더 온다. 중위 노드는 자식 트리가 언제나 정확히 둘이므로 개수를 적지 않는다.

위 트리를 이 규칙으로 적으면 다음과 같다.

-1 3 5 -3 1 -3 2 2 8 1 7 -2 8 3 9 2

뒤섞인 트리 데이터를 읽어서 트리의 값을 전위 순서로 출력하라.

입력은 여러 개의 문제로 이루어지고, 한 문제가 한 줄을 차지한다. 각 줄에는 공백으로 구분한 정수가 놓인다. 첫 번째 정수는 그 문제의 코드 값 개수 $C$ ($0 < C \le 2000$)이고, 그 뒤에 뒤섞인 트리 데이터인 정수 $V_i$ ($-3 \le V_i \le 9$)가 $C$개 온다.

트리에 담긴 숫자는 항상 0 이상 9 이하다. 음수는 순서를 알리는 코드로만 쓰인다. 자식 트리의 개수도 같은 범위에 들어가므로 한 노드의 자식 트리는 많아도 9개다.

입력의 끝은 0 하나만 있는 줄로 표시한다.

문제마다 한 줄에, 그 트리의 값을 전위 순서로 공백으로 구분해 출력한다.