说明

卢卡斯数列是与斐波那契数列类似的整数序列，区别在于初始项不同，其递推关系和通项公式均与黄金分割比例相关。该数列在数论、密码学等领域有重要应用。其递推公式为：

起始项为 $L_1=1$，$L_2=3$，后续项为前两项之和，即$L_n=L_{n−1}+L_{n−2}$。前几项依次为：$1,3,4, 7,11,18,29…$

输入格式

输入一个整数 $n$（$3 \le n \le 20$）

输出格式

输出卢卡斯数列的前 $n$ 项，每一项之间用空格隔开。

样例

6

1 3 4 7 11 18

数据范围

对于 $100\%$ 的数据，$3 \le n \le 20$。