Fractal Points on a Line Sometimes, when I'm really bored (really bored), I like to draw a line segment and draw points on it.

First, I draw a line segment of a certain size, which is 2^N for some value of N.  The line will be represented by a series of . characters.

................


Then, I plot a point at the left end.  Points will be represented by X characters.

X...............


Then, I follow a pattern.  Starting at the most recently plotted point (which I'll call A), I advance to the next plotted point (B) on the line (wrapping around as necessary).  Then, I advance to the next plotted point on the line (C).  Then, I plot a new point half-way in between this third point (C) and the next already plotted point (D).

Whenever you wrap around the line, the "middle" is determined in wrapping manner.  The newly plotted point is always to the right of C.

Let's say that the following line was my current line.  Here is how I would plot the next two points.  For this example, I'll label each important point with a letter.

X...A...X.X...X.
    ^

X...A...B.X...X.
        ^

X...A...B.C...X.
          ^

X...A...B.C...D.
            ^

X...X...X.X.A.X.
            ^

X...X...X.X.A.B.
              ^

C...X...X.X.A.B.
^

C...D...X.X.A.B.
  ^

X.A.X...X.X.X.X.
  ^


Returning to the previous example, the next point will be plotted in the middle of the line.

X.......X.......


This is perhaps a little bit of a special case: advancing to the next point simply leaves you where you started.  The only useful halfway point is the "cyclic" halfway point (the halfway point on the line), as opposed plotting a point on top of itself.   

Below is the series of points that I would plot on the line from here to the end.

X.......X.......
X.......X...X...
X.......X.X.X...
X...X...X.X.X...
X...X...X.XXX...
X.X.X...X.XXX...
X.X.X...XXXXX...


There is no longer any room to plot the next point, as it would have to be wedged between two adjacent points, so I have reached the maximum depth for the given value of N = 4.  The last line in the above list is "complete."

The Challenge

The goal is to write the shortest program/named function that will print/return the completed line for a given value of N.  The above shows N = 4.

Input

Input will be a single non-negative integer N.  The length of the generated line will then be 2^N.

Output

Output will be the completed line of length 2^N, formed by . and X characters.  A trailing newline doesn't matter.

Example I/O

0
X

1
XX

2
X.XX

3
X.X.XXX.

4
X.X.X...XXXXX...

5
X.X.X...X...X...X.XXX.XXX.......
Python 2, 137

n=input()
l=[0]*2**n;i=0
while~i%2:i=i/2%2**n;l[i]=1;i=sum([k for k,v in enumerate(l*4)if(k&gt;i)*v][1:3])
print''.join(['.X'[x]for x in l])


Quite straightforward.

Pyth, 49

More or less a translation. Main difference is that I don't use a list representing the line, I use a string. 

J*\.^2QW!%Z2K%/Z2lJ=JXJK\X=Zs&lt;tf&amp;q\X@JT&gt;TKU*4J2)J


Try it online. 

                         Q=input(); Z=0 #implicit
J*\.^2Q                  J = "."*(2^Q)
W!%Z2                    while !(Z%2):
  K%/Z2lJ                  K=(Z/2)%(len(J))
  =JXJK\X                  change J, the point at index K is changed to a "X"
       f          U*4J     filter all elements T in [0, 1, 2, ..., 4*len(J)-1]:
        &amp;q\X@JT&gt;TK           where J[T]=='X' and T&gt;K
     &lt;t               2    only us the second and third element
  =Zs                      and store the sum to Z
)J                       end while and print J