Rainw Likes Smiling

题号：NC231991
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Rainw is always smiling. So, some people who are very good had token n photos of him smiling.

Each of these photos has a classical value, and i-th photo has w_i classical value.

As time goes on, each photo will become more and more classical, the classical value of the i-th photo will become $t \times w_i$

Playf is a photo lover. He wants to know for each t, how many photos can be selected at most so that the sum of the classical value of the selected photos is a multiple of n.

输入描述:

The first line contains a single integer n $(2\le n \le 5000)$ .

The second line contains n integers $w_1,w_2,w_3,...,w_n,1\le w_i \lt n$ represents the classical value of the i-th photo.

输出描述:

For each t   print a single integer, represents the maximum number of photos Playf can select.

示例1

输入

复制

6
1 1 1 2 2 2

输出

复制

4 6 5 6 4 6