Paper Folding

When a large sheet of paper is folded in half, then in half again, and so on, with every fold parallel, and is then unfolded flat, it shows a series of parallel creases -- some pointing up, some pointing down -- dividing the paper into equal fractions of its original length. If the paper is instead opened only half-way, so that every crease forms a 90-degree angle, then, viewed end-on, it forms a dragon curve. (The curve never crosses itself, although two corners may touch.)

Write a program that draws the curve produced after N folds. The curve is specified precisely as follows. Seen from above, the paper starts flat with its start edge on the left. The right half is folded over onto the left half; then the right half of the resulting double sheet is folded onto its left half, forming a 4-thick sheet; and so on for N folds. Every fold is then opened from a 180-degree bend to a 90-degree bend, and finally the bottom edge of the paper is viewed end-on to reveal the dragon curve.

From this view, the only piece of the original paper whose orientation is unchanged is the one containing the start edge; that piece is horizontal, with the start edge at its left end. This condition defines the curve uniquely. Draw horizontal pieces with the underscore character _ and vertical pieces with the vertical-bar character |.

The input consists of several lines, each containing a single integer N ($1 \le N \le 13$). A line containing a single 0 marks the end of the input and is not processed.

For each value of N, output the corresponding dragon curve. Shift each picture as far to the left and as high as possible (so that the topmost row and the leftmost column of the picture each contain at least one character). After each curve, print a line containing a single caret ^. Note that for large N the picture is more than 80 characters wide, so it may wrap on screen.