Draw a range of mountain ranges Inspired by Fibonacci domino tiling, this problem is about generating ASCII art representing another famous combinatorial sequence.

A n-step mountain diagram is a drawing of a mountain range, using exactly n '/' and n '\' characters, such that characters sketch a continuous curve which never dips below its initial "altitude".  For example,

   /\/\
/\/    \


and

   /\
/\/  \/\


are both 4-step mountain diagrams, but

/\  /\/\
  \/


is not.

Input

The program should accept an integer n from stdin or as the parameter to a function.

Output

Print all n-step mountain diagrams to stdout. The diagrams can be in any order, but should be separated by some sort of whitespace. You can decide if different diagrams will be output horizontally, vertically, etc.

As in the domino tiling problem, you can use whatever whitespace you want. This includes extra newlines before or after the printed output.

Example

Some sample valid outputs for n=3:

Valid output A:

                                        /\
         /\             /\             /  \    /\/\
/\/\/\  /  \/\       /\/  \           /    \  /    \


Valid output B:

   /\
/\/  \

 /\/\
/    \

/\/\/\   

  /\
 /  \
/    \

 /\
/  \/\


Valid output C:

  /\
 /  \       /\
/    \   /\/  \
                  /\/\
 /\              /    \
/  \/\   /\/\/\


This is code golf; shortest program (in bytes) wins.
Python 2: 151 chars

N=2*input()
for i in range(2**N):
 L=[];c=1;exec"b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\/'[b];i=i/2*(c&gt;0);"*N
 for x in(c==1)*zip(*L):print"".join(x)

#Output for n=3:




  /\  
 /  \ 
/    \




 /\/\ 
/    \




   /\ 
/\/  \




 /\   
/  \/\





/\/\/\


Wow, this is a mess.

The first idea is to use the numbers 0 to 2**N-1 to encode all sequences of N up-moves and down-moves in their bits. We read off these bits one by one by repeated %2 and /2, iterated in an exec loop.

We store the running mountain range sideways in a transposed list of strings L. Each time, we generate a new a row of spaces are replace one space in the new row with / or \ depending on whether an up-move or down-move happened.

The index of that space is c spaces from the end, where c is the running height. Doing it from the front would make the mountains upside down. We further shift it by b to align upward and downward moves , getting [b-c]. Starting c at 1 rather than 0 fixes an off-by-one error.

To eliminate cases where c dips below the start value 1, when this happens, we set i to 0, which causes all further moves to be downward, making c become more negative. Then, when we check whether c ended at 1, we also check whether c ever fell below it. We only print the mountain range if c is 1.

To print, we do zip(*L) to transpose the range from vertical to horizontal, and print each joined string. A lot of trouble in this answer came from Python treats strings as immutable, so we worked with them as lists of characters and only joined them into strings for printing.

Thanks to @flornquake for help and improvements.