N. Not Afraid to Fall
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Luisa likes to practice on the UnBalloonforces website, where she solves problems and participates in contests. She follows the philosophy "Not Afraid to Fall", which says that one should participate in every contest, even if there is a risk of falling in title (equivalent to color on Codeforces), because that is the best way to train both skill and mindset. This worked so well that today she has the title of Super Programmer, which is the second highest on UnBalloonforces.

On UnBalloonforces, every problem has an integer rating between $$$1$$$ and $$$M$$$. As a form of training for Luisa, her coach, Ruan, prepared a list of $$$N$$$ problems with various ratings. He also sent a voice message saying: "Look, actually, just do the ones with rating greater than or equal to..." (Luisa could not hear the rating specified by Ruan).

Luisa has already solved all the problems, and now she is bored. Remembering the message, she wondered: "If the rating chosen by Ruan were $$$i$$$, what would be the sum of the ratings of the problems I should solve?" Help satisfy Luisa's curiosity by calculating this sum for every $$$i$$$ from $$$1$$$ to $$$M$$$!

Input

The first line of the input contains two integers: $$$N$$$ and $$$M$$$, the number of problems in Luisa's list and the maximum rating of a problem on UnBalloonForces $$$(1 \leq N, M \leq 5 \cdot 10^5)$$$.

The second line of the input contains $$$N$$$ integers $$$r_i$$$: the $$$i$$$-th of them represents the rating of the $$$i$$$-th problem in the list $$$(1 \leq r_i \leq M)$$$.

Output

Print, on a single line, $$$M$$$ integers: the $$$i$$$-th of them must be the sum of the ratings of the problems Luisa would have to solve if Ruan had specified rating $$$i$$$.

Examples
Input
5 5
2 4 2 4 2
Output
14 14 8 8 0
Input
3 2
1 1 2
Output
4 2
Input
8 9
5 9 1 2 3 4 7 6
Output
37 36 34 31 27 22 16 9 9
Note

In the first test case, if the rating specified by Ruan had been $$$1$$$ or $$$2$$$, Luisa would need to solve all the problems, resulting in a sum of ratings equal to $$$14$$$. If the specified rating were $$$3$$$ or $$$4$$$, Luisa would not need to solve the problems with rating $$$2$$$, only the two with rating $$$4$$$, and the sum would be only $$$8$$$. Finally, if the specified rating were $$$5$$$, Luisa would not need to solve any problem (sum $$$0$$$).