Constructing Numbers with Sum Equal to LCM and Minimal Range

Given a positive integer n, construct n positive integers \(a_1,a_2,\dots,a_n\) such that

\(\sum_{i=1}^n a_i = \operatorname{lcm}(a_1,a_2,\dots,a_n)\)

where \(\operatorname{lcm}\) denotes the least common multiple. In addition, the constructed sequence must have the smallest possible range (i.e. the difference between the maximum and minimum value among the \(a_i\)) among all sequences satisfying the above equality.

Important: The least common multiple of your constructed numbers must not exceed \(10^{12}\); otherwise the SPJ may incur undefined behavior.

Note: It can be proven that no solution exists when n = 2. For this problem, you should output -1 if no valid sequence exists. (For n = 1, output 1.)

Hint: Since every \(a_i\) divides \(L = \operatorname{lcm}(a_1, a_2, \dots, a_n)\), we may write \(a_i = \frac{L}{b_i}\) for some positive integer \(b_i\). The equality becomes

\(\sum_{i=1}^n \frac{1}{b_i} = 1\).

One simple construction for n \ge 3 is to set:

• \(b_1 = 2,\; b_2 = 3\), and
• for \(i = 3,4,\dots,n\), let \(b_i = 6(n-2)\).

Then, taking \(L = \operatorname{lcm}(2, 3, 6(n-2)) = 6(n-2)\), we define

• \(a_1 = \frac{6(n-2)}{2} = 3(n-2)\),
• \(a_2 = \frac{6(n-2)}{3} = 2(n-2)\), and
• \(a_i = \frac{6(n-2)}{6(n-2)} = 1 \quad (i=3,4,\dots,n)\).

It is straightforward to check that

• \(\sum_{i=1}^n a_i = 3(n-2)+2(n-2)+(n-2) = 6(n-2) = L\), and
• \(\operatorname{lcm}(3(n-2),2(n-2),1,\dots,1) = 6(n-2) = L\).

The range of this sequence is \(3(n-2)-1\), which is minimal for this construction. Use this or any other correct method.

inputFormat

The input consists of a single line containing one positive integer n (1 \le n \le 10^6).

outputFormat

If a valid sequence exists, output n positive integers separated by spaces representing \(a_1,a_2,\dots,a_n\) which satisfy \(\sum_{i=1}^n a_i = \operatorname{lcm}(a_1,a_2,\dots,a_n)\) and have the minimal range among all valid sequences. If no valid sequence exists (this happens when n = 2), output -1.

sample

1

1