描述

联欢会上，主持人先在黑板上写了四个数字，分别是：2，0，1，9，然后说：“这串数字从第五个数起，每一个数都是它前四数字之和的个位数字”。请你打印输出这个数列的前 N 项，并计算前 N 项的和。

输入格式

单个整数：表示项数 N。

输出格式

第一行：N 个数字，表示所求数列的前 N 项。

第二行：单个数字，表示前 N 项数字的和。

数据范围

1 ≤ N ≤ 100000。

样例