The Lucas-nacci Numbers Background

Most everyone is familiar with the Fibonacci numbers F(n):


  0, 1, 1, 2, 3, 5, 8, 13, 21 ...


These are formed by the recursion function F(n) = F(n-1) + F(n-2) with F(0)=0 and F(1)=1. A000045

A closely related sequence is the Lucas numbers L(m):


  2, 1, 3, 4, 7, 11, 18, 29 ...


These are formed by the recursion function L(m) = L(m-1) + L(m-2) with L(0)=2 and L(1)=1. A000032

We can alternate between the two sequences based on even/odd indices, with the construction
A(x) = F(x) if x mod 2 = 0 and A(x) = L(x) otherwise. For example, A(4) is equal to F(4) since 4 mod 2 = 0. We'll call this sequence the Lucas-nacci Numbers, A(x):


  0, 1, 1, 4, 3, 11, 8, 29, 21, 76 ...


This can be formed by the recursion function A(x) = 3*A(x-2) - A(x-4) with A(0)=0, A(1)=1, A(2)=1, and A(3)=4. A005013

Challenge

Given input n, output the sequence of n+1 numbers up to and including A(n) as described above. Fewest bytes (or byte-equivalents, such as for LabVIEW, as determined individually on Meta) wins.

Input

A single non-negative integer n.

Output

A list of numbers that correspond to the subsequence of Lucas-nacci numbers from A(0) to A(n). The list must be in sequential order as described above.

Rules


Standard code-golf rules and loophole restrictions apply.
Standard input/output rules apply.
Input number can be in any suitable format: unary or decimal, read from STDIN, function or command-line argument, etc. - your choice.
Output can be printed to STDOUT or returned as a result of the function call. If printed, suitable delimiters to differentiate the numbers must be included (space-separated, comma-separated, etc.).
Additionally, if output to STDOUT, surrounding whitespace, trailing newline, etc. are all optional.
If the input is a non-integer or a negative integer, the program can do anything or nothing, as behavior is undefined.


Examples

Input -&gt; Output
0 -&gt; 0
5 -&gt; 0, 1, 1, 4, 3, 11
18 -&gt; 0, 1, 1, 4, 3, 11, 8, 29, 21, 76, 55, 199, 144, 521, 377, 1364, 987, 3571, 2584
Jelly, 12 bytes

;2U+¥Ð¡-,1ZḢ


Try it online!

Background

We can extend F and L to -1 by defining F(-1) = 1 and L(-1) = -1. This is consistent with the recursive function.

Our program starts with

-1  1
 0  2


In each step, to form the next pair, we reverse the last pair and add it to the penultimate pair. For example:

[0, 2] U+¥ [-1, 1] -&gt; [2, 0] + [-1, 1] -&gt; [1, 1]


If we continue this process for a few more steps, we get

-1  1
 0  2
 1  1
 1  3
 4  2
 3  7
11  5


The Lucas-nacci sequence is simply the left column.

How it works

;2U+¥Ð¡-,1ZḢ  Niladic link. No implicit input.
              Since the link doesn't start with a nilad, the argument 0 is used.

;2            Concatenate the argument with 2, yielding [0, 2].
       -,1    Yield [-1, 1]. This is [L(-1), F(-1)].
    ¥         Create a dyadic chain of the two atoms to the left:
  U             Reverse the left argument.
   +            Add the reversed left argument and the right one, element-wise.
     Ð¡       For reasons‡, read a number n from STDIN.
              Repeatedly call the dyadic link U+¥, updating the right argument with
              the value of the left one, and the left one with the return value.
              Collect all intermediate results.
          Z   Zip the list of results, grouping the first and seconds coordinates.
           Ḣ  Head; select the list of first coordinates.


‡ Ð¡ peeks at the two links to the left: 2 and U+¥. Since the leftmost one is a nilad, it cannot be the body of the loop. Therefore, U+¥ is used as body and a number is read from input. Since there are no command-line arguments, that number is read from STDIN.