종이 접기

큰 종이를 반으로 접고, 다시 반으로 접기를 반복한다. 모든 접힌 선(주름)은 서로 평행하다. 종이를 완전히 펼치면 위로 솟은 주름과 아래로 파인 주름이 번갈아 나타나며, 종이를 원래 길이의 여러 등분으로 나눈다. 대신 종이를 절반만 펼쳐서 모든 주름이 정확히 90도를 이루도록 하면, 이를 옆에서(단면으로) 바라볼 때 용 곡선(dragon curve) 이 만들어진다. (이 곡선은 자기 자신과 교차하지 않지만, 두 모서리가 맞닿을 수는 있다.)

N번 접은 뒤 나타나는 곡선을 그리는 프로그램을 작성하라. 곡선은 다음과 같이 정확하게 정의된다. 위에서 내려다본 종이는 처음에 평평하며, 시작 모서리(start edge) 가 왼쪽에 있다. 오른쪽 절반을 왼쪽 절반 위로 접고, 이렇게 두 겹이 된 종이의 오른쪽 절반을 다시 왼쪽 위로 접어 네 겹으로 만들며, 이 과정을 N번 반복한다. 그런 다음 모든 접힌 부분을 180도 굽힘에서 90도 굽힘으로 편다. 마지막으로 종이의 아래쪽 가장자리를 단면으로 바라보면 용 곡선이 나타난다.

이 시점에서 원래 종이 중 방향이 바뀌지 않은 유일한 조각은 시작 모서리 를 포함한 조각이며, 이 조각은 수평이고 시작 모서리가 그 왼쪽 끝에 있다. 이 조건이 곡선을 유일하게 결정한다. 수평 조각은 밑줄 문자 _ 로, 수직 조각은 세로줄 문자 | 로 그린다.

입력은 여러 줄로 이루어지며, 각 줄에는 정수 N ($1 \le N \le 13$) 하나가 주어진다. 0 하나만 있는 줄은 입력의 끝을 나타내며, 이 값은 처리하지 않는다.

각 N 값에 대해 해당하는 용 곡선을 출력한다. 각 그림은 가능한 한 왼쪽으로, 그리고 가능한 한 위로 붙여서 출력한다(그림의 맨 윗줄과 가장 왼쪽 열에 각각 문자가 하나 이상 있어야 한다). 각 곡선을 출력한 뒤에는 캐럿 문자 ^ 하나만 있는 줄을 출력한다. N이 크면 그림의 너비가 80자를 넘으므로 화면에서 줄이 넘칠 수 있다.