Variable Length Encoding of Positive Integers

Little Ming recently learned three ways to represent integers: sign-magnitude, ones' complement, and two's complement. He noticed that although computers often use two's complement to represent integers (e.g. using 4 bytes to represent numbers in the range $0$ to $100$ even though $2^{31}-1$ is much larger), this can be wasteful for small numbers. Through research, he discovered a variable-length encoding method for positive integers. The rules for this encoding are as follows:

1. Express the given positive integer in its binary form. For example, $0_{10}$ is $0_{2}$ and $926_{10}$ is $1110011110_{2}$.
2. Split the binary representation into groups of 7 bits starting from the least significant bit (LSB). If the highest group has less than 7 bits, pad it on the left with zeros. For instance, $0$ is padded to 0000000, and $1110011110_{2}$ is split into two groups: 0011110 (low-order group) and 0000111 (high-order group).
3. For each group, add a prefix bit. Starting from the group representing the LSB, prefix it with a 1 if it is not the last (i.e. the most significant) group; if it is the last group, prefix it with a 0. For example, the encoding of $0$ is 00000000 (one byte), and the encoding of $926$ is two bytes: 10011110 (from 0011110) and 00000111 (from 0000111).

This encoding method uses fewer bytes for smaller numbers while still being able to represent very large numbers. For instance, the number $987654321012345678$ has a binary representation grouped as $$0001101 \quad 1011010 \quad 0110110 \quad 1001011 \quad 1110100 \quad 0100110 \quad 1001000 \quad 0010110 \quad 1001110, $$

resulting in an encoding that (when expressed in hexadecimal) is: CE 96 C8 A6 F4 CB B6 DA 0D (i.e. 9 bytes).

Your task is to write a program that takes a positive integer as input and outputs its variable-length encoding. In the output, each byte should be represented as an 8-character binary string. If the encoding consists of multiple bytes, output the bytes in order from the group representing the least significant 7 bits to the group representing the most significant bits, with each byte separated by a space.

inputFormat

A single line containing a positive integer N (0 ≤ N ≤ 10^18). Note that even though the problem statement refers to positive integers, the number 0 is also included for encoding purposes.

outputFormat

Output the variable-length encoding of the given number. Each byte should be represented as an 8-bit binary string. If there are multiple bytes, separate them by a single space.

sample

0

00000000