Generate Pascal's Braid This is Pascal's Braid:

 1 4  15  56   209   780    2911    10864     40545      151316      564719
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719


I totally made that up. Blaise Pascal didn't have a braid as far as I can tell, and if he did it was probably made of hair instead of numbers.

It's defined like this:


The first column has a single 1 in the middle.
The second column has a 1 at the top and at the bottom.
Now we alternate between putting a number in the middle or two copies of a number at the top and bottom.
If the number goes on the top or the bottom, it will be the sum of the two adjacent numbers (e.g. 56 = 15 + 41). If you tilt your head a little, this is like a step in Pascal's triangle.
If the number goes in the middle, it will be the sum of all three adjacent numbers (e.g. 41 = 15 + 11 + 15).


Your task will be to print (some part of) this braid.

Input

You should write a program or function, which receives a single integer n, giving the index of the last column to be output.

You may choose whether the first column (printing only a single 1 on the middle line) corresponds to n = 0 or n = 1. This has to be a consistent choice across all possible inputs.

Output

Output Pascal's Braid up to the nth column. The whitespace has to match exactly the example layout above, except that you may pad the shorter line(s) to the length of the longer line(s) with spaces and you may optionally output a single trailing linefeed.

In other words, every column should be exactly as wide as the number (or pair of equal numbers) in that column, numbers in successive columns should not overlap and there should be no spaces between columns.

You may either print the result to STDOUT (or the closest alternative), or if you write a function you may return either a string with the same contents or a list of three strings (one for each line).

Further Details

You may assume that n won't be less than the index of the first column (so not less than 0 or 1 depending on your indexing). You may also assume that the last number in the braid is less than 256 or the largest number representable by your language's native integer type, whichever is greater. So if your native integer type can only store bytes, you can assume that the largest n is 9 or 10 (depending on whether you use 0- or 1-based n) and if it can store signed 32-bit integers, n will be at most 33 or 34.

Standard code-golf rules apply. The shortest code wins.

OEIS

Here are a few relevant OEIS links. Of course, these contain spoilers for different ways to generate the numbers in the braid:


Top/bottom: A001353 or A010905 or A106707 or A195503
Middle: A001835 or A079935
Both: A002530


Test Cases

These test cases use 1-base indexing. Each test case is four lines, with the first being the input and the remaining three being the output.

1

1

---
2
 1
1
 1
---
3
 1
1 3
 1
---
5
 1 4
1 3 11
 1 4
---
10
 1 4  15  56   209
1 3 11  41  153
 1 4  15  56   209
---
15
 1 4  15  56   209   780    2911
1 3 11  41  153   571   2131    7953
 1 4  15  56   209   780    2911
---
24
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
1 3 11  41  153   571   2131    7953     29681     110771      413403      1542841
 1 4  15  56   209   780    2911    10864     40545      151316      564719       2107560
Pyth, 44 bytes

The number generation took 20 bytes, and the formatting took 24 bytes.

jsMC+Led.e.&lt;bkC,J&lt;s.u+B+hNyeNeNQ,1 1Qm*;l`dJ


Try it online!

jsMC+Led.e.&lt;bkC,J&lt;s.u+B+hNyeNeNQ,1 1Qm*;l`dJ   input as Q
                   .u          Q,1 1           repeat Q times, starting with [1,1],
                                               collecting all intermediate results,
                                               current value as N:
                                               (this will generate
                                                more than enough terms)
                       +hNyeN                  temp &lt;- N[0] + 2*N[-1]
                     +B      eN                temp &lt;- [temp+N[-1], temp]

now, we would have generated [[1, 1], [3, 4], [11, 15], [41, 56], ...]

jsMC+Led.e.&lt;bkC,J&lt;s                 Qm*;l`dJ
                  s                            flatten
                 &lt;                  Q          first Q items
                J                              store in J
                                     m    dJ   for each item in J:
                                         `     convert to string
                                        l      length
                                      *;       repeat " " that many times

jsMC+Led.e.&lt;bkC,
              C,     transpose, yielding:
[[1, ' '], [1, ' '], [3, ' '], [4, ' '], [11, '  '], ...]
(each element with as many spaces as its length.)
        .e            for each sub-array (index as k, sub-array as b):
          .&lt;bk            rotate b as many times as k

[[1, ' '], [' ', 1], [3, ' '], [' ', 4], [11, '  '], ...]

jsMC+Led
    +Led              add to each sub-array on the left, the end of each sub-array
   C                  transpose
 sM                   sum of each sub-array (reduced concatenation)
j                     join by new-lines