Danny is a very hardworking student at A. Y. Johnson Secondary School. Due to an unfortunate birth defect, he was born with an unusual number of hands and he is unable to wear a backpack. Thus, he must carry all of his textbooks with his many hands when walking to his classes. Importantly, Danny wants to make sure that the weight on each of his hands is as equal as possible.

Given \(H\) identical hands that Danny has and \(N\) textbooks that Danny must carry, each with a weight \(w_j\), determine an optimal way to balance his textbooks. That is, determine a distribution of textbooks that minimizes the total imbalance, \(\sum^{H}_{i=1}|s_i-A|\) where \(s_i\) is the total weight held by the \(i^{th}\) hand and \(A\) is the average weight held by each hand.

*Note: each textbook may be carried by only one hand.

Constraints

\(H \le N \le 10H\)

\(1 \le w_j \le 10^6\)

Subtask 1 [71%]

\(2 \le H \le 10^4\)

Subtask 2 [29%]

\(10^4 \le H \le 10^5\)

Input Specification

The first line of input will contain the two integers \(H\) and \(N\).

The second line of input will contain \(N\) integers, each representing \(w_j\), the weight of the \(j^{th}\) textbook.

Output Specification

Output \(H\) lines, representing each hand, with the \(i^{th}\) line containing \(s_i\), the total weight of every textbook held by the \(i^{th}\) hand. The ordering may be arbitrary.

Sample Input

6 10
1 11 5 3 8 9 13 8 1 1

Sample Output

9
9
9
9
11
13

Explanation for Sample Output

The \(i^{th}\) hand is holding textbooks with the following weights:

Hand 1: 9
Hand 2: 8 1
Hand 3: 8 1
Hand 4: 5 3 1
Hand 5: 11
Hand 6: 13

The total imbalance of this state is:

\(\sum^{H}_{i=1}|s_i-A|=|9-10|+|9-10|+|9-10|+|9-10|+|11-10|+|13-10|=1+1+1+1+1+3=8\)

It can be shown that this is minimal.