트리

트리는 컴퓨터 과학에서 아주 자주 등장한다. 자연의 나무와 달리 컴퓨터 과학의 트리는 위아래가 뒤집힌 채로 자란다. 뿌리(root)가 맨 위에 있고 잎(leaf)이 맨 아래에 있다.

트리는 노드(node) 들로 이루어진다. 그중 하나가 뿌리 다. 뿌리가 아닌 모든 노드 $w$ 에는 아버지 $v$ 가 정확히 하나 있다. $v$ 가 $w$ 의 아버지이면 $w$ 는 $v$ 의 아들 이다. 아들이 없는 노드를 잎 이라 한다. 노드 $w$ 의 아들들, 그 아들들의 아들들, 이렇게 계속 이어지는 노드들을 $w$ 의 자손 이라 한다. 뿌리를 제외한 모든 노드는 뿌리의 자손이다.

각 노드에는 레벨 번호 가 붙는다. 뿌리의 레벨은 $0$ 이고, 아들의 레벨은 아버지의 레벨보다 $1$ 크다.

모든 노드가 아들을 정확히 두 개 갖거나 하나도 갖지 않을 때, 그 트리를 완전 이진 트리(complete binary tree) 라 한다. 이진 트리에서 두 아들은 각각 왼쪽 과 오른쪽 이라 부른다.

아래 그림은 완전 이진 트리의 예다. 노드들은 전위 순회(preorder) 순서로 번호가 매겨져 있다. 이 순서에서 뿌리는 번호 $1$ 을 받고, 아버지는 자기 아들들보다 앞선 번호를 받으며, 왼쪽 아들과 그 모든 자손은 오른쪽 아들과 그 모든 자손보다 작은 번호를 받는다.

이렇게 번호가 매겨진 완전 이진 트리는 여러 방식으로 적을 수 있다. 그중 세 가지를 소개한다.

계보 표현(genealogical representation).\ 숫자들의 수열이다. 첫 번째 원소는 $0$ 이고, $j > 1$ 인 경우 $j$ 번째 원소는 노드 $j$ 의 아버지의 번호다.

괄호 표현(bracket representation).\ 각 노드는 괄호로 이루어진 문자열에 대응된다. 잎은 () 에 대응된다. 그 밖의 노드 $w$ 는 (lr) 에 대응되며, 여기서 l 과 r 은 각각 $w$ 의 왼쪽 아들과 오른쪽 아들에 대응되는 문자열이다. 뿌리에 대응되는 문자열이 트리 전체의 괄호 표현이다.

레벨 표현(level representation).\ 위에서 정한 번호 순서대로 나열한 잎들의 레벨 번호 수열이다.

그림의 트리는 다음과 같이 나타낼 수 있다.

숫자 수열을 읽어서, 그것이 어떤 완전 이진 트리의 레벨 표현인지 판정하는 프로그램을 작성하라. 아니라면 NIE("아니오")라는 한 단어를 출력한다. 맞다면 그 트리의 나머지 두 표현, 즉 계보 표현과 괄호 표현을 출력한다.

첫째 줄에는 수열의 원소 개수를 나타내는 양의 정수 $m$ 이 주어진다 ($m \le 2500$). 둘째 줄에는 그 $m$ 개의 원소가 공백 하나로 구분되어 주어진다.

입력은 항상 올바른 형식으로 주어지므로, 프로그램이 형식을 따로 검사할 필요는 없다.

다음 중 하나를 출력한다.

• 한 단어 NIE, 또는
• 두 줄: 첫째 줄에는 계보 표현을 공백 하나로 구분하여 출력하고, 둘째 줄에는 괄호 표현을 공백 없이 ( 와 ) 로 이루어진 문자열로 출력한다.