题目描述

Elly 有一把很特别的尺子，长度恰好为 L 厘米，并且在若干个整数位置上刻有刻度（不一定每个整数位置都有）。尺子的起点 0 和终点 L 一定有刻度。

这把尺子最特别的性质是：任意两枚刻度之间的距离两两不同。

更形式化地说，若尺子上共有 N 个刻度，位置为：

0 = A1 < A2 < ... < AN = L

那么对于任意满足 i < j 的下标，只有在 (i, j) = (p, k) 时，才允许：

Aj - Ai = Ak - Ap

也就是说，所有两两距离必须互不相同。

现在 Elly 想构造一把拥有 N 个刻度的这种尺子，并且要求总长度 L 尽可能小。

请输出任意一种最短构造。

输入格式

输入一行，一个整数 N，表示尺子上的刻度数（包含起点与终点）。

输出格式

输出一行 N 个非负整数，按严格递增顺序给出各个刻度的位置。

要求：

• 第一个数必须为 0；
• 最后一个数必须为最小可能的 L；
• 若有多种最优方案，输出任意一种即可。

数据范围

• 5 <= N <= 14

评分方式

每个测试点单独计分。

样例

输入 1

5

输出 1

0 2 7 8 11

说明 1

当 N = 5 时，最短长度为 11。上述构造中，各对刻度之间的距离集合为：

{2, 7, 8, 11, 5, 6, 9, 1, 4, 3}

它们互不相同。

例如，0 1 4 9 11 也是一种合法最优解。

输入 2

8

输出 2

0 1 4 9 15 22 32 34