Background

Special for beginners, ^_^

Description

有一个已排序好的数组：
1 4 6 9 13 16 19 28 40 100
输入一个数，将输入的数按照排序规律插入这个数组。

Format

Input

输入一个数，插入到它应该被排序的位置。

Output

输出插入后排序的数组

Sample 1

Input

2

Output

1 2 4 6 9 13 16 19 28 40 100
这里将 2 插入到第二个位置

Limitation

1s, 1024KiB for each test case.