Bajtazar has amassed a large collection of postage stamps. He is not as interested in them as he was in his youth, so he has decided to give his collection away to younger philately enthusiasts. However, he would like to do this as fairly as possible, and for this, he needs your help.
Bajtazar's collection consists of $n$ stamps, where the $i$-th stamp comes from city $a_i$. For simplicity, cities are denoted by integers. Bajtazar intends to place an advertisement in the newspaper stating that he plans to give away his collection. If $k$ enthusiasts apply, he will present each of them with some subset of stamps, subject to a certain condition: every enthusiast must receive the same multiset of stamps. This means that for any two enthusiasts and for any city, both enthusiasts must receive the same number of stamps from that city. In particular, this may mean that Bajtazar does not give away any stamps at all.
Bajtazar does not know exactly how many enthusiasts will apply. Therefore, for every number $k$ in the range from $1$ to $n$, you must determine the maximum number of stamps Bajtazar can give away if $k$ enthusiasts apply.
Input
The first line of input contains a single integer $n$ ($1 \le n \le 300\,000$), representing the number of stamps in Bajtazar's collection.
The second line of input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the city numbers from which Bajtazar's stamps originate.
Output
The single line of output should contain $n$ integers separated by single spaces; the $k$-th of these should be equal to the maximum number of stamps Bajtazar can give away if $k$ enthusiasts apply.
Examples
Input 1
9 1 1 777 42 777 1 42 1 777
Output 1
9 8 6 4 0 0 0 0 0
Note
If one enthusiast applies to Bajtazar, Bajtazar can give them all his stamps.
If there are two enthusiasts, Bajtazar can give them two stamps from city 1, one stamp from city 42, and one stamp from city 777 each, for a total of 8 stamps.
If there are four enthusiasts, Bajtazar can give them one stamp from city 1 each.
If there are more than four enthusiasts, Bajtazar will not be able to give away any stamps.