You are given positive integer $n$. Construct any array $a_1, a_2, \dots a_n$, such that:

• $0 \le a_i \le 30000$
• For all pairs $i, j$ such that $1 \le i \le j \le n$, the values of $a_i + a_{i+1} + \dots + a_{j}$ should be distinct.

Input format 

• The single line  contains integer $n$ - the length of the array.

Output format

• Find any array such that all of the conditions are hold.

Constraints

•     $1 \le n \le 5*10^3$