In this problem, as in problem B, Petya takes his M-pawed Beast for a walk again (however, the number of paws the Beast can have up to 1000 in this problem). Again, his mother left him N pants with respectively K
1, K
2, …, K
N pants. However, grouse Petya wants to put pants on the Beast so that the following conditions are met:
- Each paw was wearing at least one trouser leg (guaranteed that this is always possible),
- number of pants worn on the most "insulated" paw should differ as little as possible from the number of pants worn on the lightest paw (when the number of pants worn on different paws is very different, the Beast feels discomfort),
- Unlike task B, Petya is not obliged to put on the Beast all available pants — some of them can be left at home.
As before, any pants can be worn on any set of paws. In particular, you can't wear multiple legs of the same pants on the same Beast's paw.
Help Petya – write a program that for each paw will indicate how many pants should be worn on it.
Input
The number M is entered first, and then the number N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Next, N numbers Ki are entered, denoting the number of pants for the pants left by the mother (1 ≤ K
i ≤ M). The sum of all Ki is not less than M.
Imprint
Print M lines, the i-th line should contain the number of pants worn on the i-th paw. If there are several answers you are looking for, then print any of them.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4 3
1 2 3
| 1
1
1
1 |
First pants worn on paw 1;
we do not use second pants;
the third pants are worn on paws 2, 3 and 4.
Thus, on all paws 1 pant. |
| 2 |
4 2
3 2 |
2
1
1
1 |
First pants worn on legs 1, 2 and 3;
the second pants are worn on legs 1 and 4.
Thus, the number of pants on the most "insulated" paw (this is paw number 1) – 2, and on the remaining paws, one leg each, i.e. the number of trousers on different paws differs by one. It is easy to see that in this example it is impossible to dress the animal in such a way that all legs have equal trouser legs, so this answer is optimal. |