Counting Bits

MediumBit-ManipulationDynamic-ProgrammingCounting5 hidden tests

For each integer i from 0 to n inclusive, compute the number of 1-bits in the binary representation of i, and output all n + 1 counts in order.

Input format

One line: a non-negative integer n.

Output format

One line: n + 1 space-separated integers; the i-th is the number of set bits in i.

Constraints

0 <= n <= 100000

Examples

Example 1

Input

Expected

0 1 1 2 1 2

Explanation

Counts for 0..5 are 0,1,1,2,1,2.

Example 2

Input

Expected

Explanation

Only 0 itself, which has zero set bits.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →