题解

题面描述

给定一个数组包含 $n$ 个整数：$\{a_1,a_2,\ldots,a_n\}$。对于每个整数 $a_i$，如果它可以表示为恰好 $k$ 个 $2$ 的幂次之和，则称 $a_i$ 是 $k$ 和谐的。注意，允许相同的 $2$ 的幂次重复使用。例如：

• $9$ 可以表示为 $1+2+2+4$，所以 $9$ 是 $4$ 和谐的。
• 同时 $9$ 也可以表示为 $1+8$，所以 $9$ 也是 $2$ 和谐的。

要求依次统计 $1$ 和谐、$2$ 和谐、$\ldots$、$30$ 和谐的数字个数。

题目内容

小美有 $n$ 个整数 {$a_1,a_2,...,a_n$}，对于第 $i$ 个数字 $a_i$ ，如果其能被 $k$ 个 $2$ 的幂次数之和表示，那么定义 $a_i$ 是 $k$ 和谐的。例如：$9$ 是 $4$ 和谐的，因为 $9=1+2+2+4$ 成立，同时也是 $2$ 和谐的，因为 $9=1+8$ 成立。

现在，你需要依次输出 $1$ ~ $30$ 和谐的数字有多少个。

输入描述

第一行输入一个整数 $n(1≦n≦2×10^5)$代表数组中的元素数量。

第二行输入 $n$ 个整数

$a_1,a_2,...,a_n(0≦a_i≦10^9)$代表初始数组。

输出描述

在一行上输出 $30$ 个整数，依次代表 $1,2,...,30$ 和谐的数字个数。

样例1

输入

3
1 2 3

输出

2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0