Given an integer n, return an array ans of length n + 1 such that for each i (0 ≤ i ≤ n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: 2
Output: 0 1 1

Example 2:

Input: 5
Output: 0 1 1 2 1 2

Constraints:

• 0 ≤ n ≤ 10⁵

Input format: A single integer n.

Output format: n+1 space-separated integers.