There are n doors numbered 1 to n and n people numbered 1 to n. Every door is…

There are n doors numbered 1 to n and n people numbered 1 to n. Every door is closed to begin with. The people act one after another, from person 1 up to person n. Person i toggles the status of every ith door, that is, every door whose number is a multiple of i: a closed door becomes open and an open door becomes closed. After all n people have acted exactly once, print the final status of all n doors, where 1 means open and 0 means closed.

Input format: The only token on standard input is the integer n.

Output format: Print n values separated by single spaces, the final status of door 1, door 2, ..., door n in that order, where 1 means open and 0 means closed, followed by a newline.

Examples:

Input: 3
Output: 1 0 0
Explanation: Every door starts closed, so the status is (0 0 0). Person 1 toggles doors 1, 2 and 3, giving (1 1 1). Person 2 toggles door 2, giving (1 0 1). Person 3 toggles door 3, giving (1 0 0).

Input: 2
Output: 1 0
Explanation: Every door starts closed, so the status is (0 0). Person 1 toggles doors 1 and 2, giving (1 1). Person 2 toggles door 2, giving (1 0).

Constraints:

• 1 ≤ n ≤ 104