Problem
If a large sheet of paper is folded in half, then in half again, etc, with all the folds parallel, then opened up flat, there are a series of parallel creases, some pointing up and some down, dividing the paper into fractions of the original length. If the paper is only opened halfway'' up, so every crease forms a 90 degree angle, then (viewed endon) it forms a
dragon curve’’. For example, if four successive folds are made, then the following curve is seen (note that it does not cross itself, but two corners touch):
Write a program to draw the curve which appears after N folds. The exact specification of the curve is as follows:
 The paper starts flat, with the ``start edge’’ on the left, looking at it from above.
 The right half is folded over so it lies on top of the left half, then the right half of the new double sheet is folded on top of the left, to form a 4thick sheet, and so on, for N folds.
 Then every fold is opened from a 180 degree bend to a 90 degree bend.
 Finally the bottom edge of the paper is viewed endon to see the dragon curve.
From this view, the only unchanged part of the original paper is the piece containing the start edge
, and this piece will be horizontal, with the start edge
on the left. This uniquely defines the curve. In the above picture, the start edge
is the left end of the rightmost bottom horizontal piece (marked s
). Horizontal pieces are to be displayed with the underscore character _
, and vertical pieces with the 
character.
Input
Input will consist of a series of lines, each with a single number N (1 <= N <= 13). The end of the input will be marked by a line containing a zero.
Output
Output will consist of a series of dragon curves, one for each value of N in the input. Your picture must be shifted as far left, and as high as possible. Note that for large N, the picture will be greater than 80 characters wide, so it will look messy on the screen. The pattern for each different number of folds is terminated by a line containing a single `^’.
Sample input


Sample output


Solution
題目描述：
將一個長條紙水平擺放，接著將右手邊的紙摺疊到左上邊的紙上面，接著又再重複做幾次，直到 N
次 ( 若將其攤平則會有 2^{N} 個折疊區塊 )。摺疊完後，依序將其攤開，攤開的方式為：將前一次摺疊的 (想像與 s
重疊的那一片) 從 180 度旋轉到 90 度位置，依序攤開 N 次。
題目解法：
這一題就是題目理解麻煩點，但是不難發現肯定是有遞迴需要處理的。
假設我們定義展開的每一根，分別為往上下左右的射線，會發現其對應關係，新的尾會跟舊的頭對照，依序對照到中間部分。
最後得到關係
 上 變成 左
 下 變成 右
 左 變成 下
 右 變成 上
輸出處理方面，利用一個 map 結構去完成。

