题目描述

春暖花开之际，兔猫信奥学院的小兔、小猫和加菲老师在校园里举办了一场“数字之旅”比赛。比赛规定：给定一个整数 n，对于所有 i 从 0 到 n，统计其二进制表示中 1 的个数，作为“魔法能量值”。最终，小兔和小猫要将所有能量值一一列出，看看谁的速度更快！

加菲老师说：“只用一次扫描、O(n) 时间就能完成哦，同学们快来挑战吧！”

输入格式

n

• 一行，一个整数 n，表示要计算的范围上限。

输出格式

ans[0] ans[1] … ans[n]

• 一行 n+1 个整数，用空格分隔，第 i 个数 ans[i] 表示 i 的二进制 1 的个数。

样例输入

5

样例输出

0 1 1 2 1 2

数据范围

0 ≤ n ≤ 100000