Maths

Time limit1sMemory limit1024 MB

Summary

Given n, find integers a_1 to a_n, each between 1 and 300, so that every prefix sum for k from 2 to n has exactly a_k divisors, or report Impossible.

Level: Medium5 of 10
Topics: Number theory, Math, Brute force
Solved: No attempts yet

Statement

Android Vasya attends Maths classes. His group started to study number theory recently. The teacher gave them several tasks as homework. One of them is as follows.

There is an integer $n$ . The problem is to find a sequence of integers $a_1, \ldots, a_n$ such that for every $k$ from 2 to $n$ , the sum $a_1 + \ldots + a_k$ has exactly $a_k$ different positive divisors. Help Vasya solve this task.

Input

The only line contains an integer $n$ ( $2 \leq n \leq 100\,000$ ).

Output

If there is no such sequence, output Impossible. Otherwise, output the space-separated integers $a_1, \ldots, a_n$ ( $1 \leq a_i \leq 300$ ).

Examples1

Example 1
Input
```
3
```
Expected output
```
1 3 4
```