Swaps with Maximum Sum

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

You are given an array \(a_1, a_2, \ldots, a_{2n}\) of length \(2n\). In one operation, you can choose any index \(i\) such that \(1 \leq i \leq 2n-1\) and swap \(a_i, a_{i+1}\).

For each \(k\) from \(0\) to \(n^2\), find the maximum possible sum \(a_1 + a_2 + \ldots + a_n\) that can be obtained after performing at most \(k\) operations.

Input

The first line contains a single integer \(n\).

The second line contains \(2n\) integers \(a_1, a_2, \ldots, a_{2n}\) — the elements of the array.

Output

Output \(n^2 + 1\) integers: the maximum possible sum \(a_1 + a_2 + \ldots + a_n\) that can be obtained by performing at most \(0, 1, 2, \ldots, n^2\) operations.

Constraints

\(1 \leq n \leq 100\),

\(1 \leq a_i \leq 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 2 3 4 5 6	6 7 8 9 10 11 12 13 14 15

Notes

If no operations are performed, the sum is \(a_1 + a_2 + a_3 = 1 + 2 + 3 = 6\).

In one operation, you can swap \(a_3, a_4\), obtaining \(a_1 + a_2 + a_3 = 1 + 2 + 4 = 7\).