Variable-Length Encoding

Problem Description

(This problem is paired with a set of multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1130.)

Xiaoming has just learned three ways of representing integers — sign-magnitude, ones' complement, and two's complement — and learned that computers usually store integers in two's complement. But it always bothers him that everyday numbers like $0 \sim 100$ still take a whole 4-byte two's-complement word, which feels wasteful.

After some searching, Xiaoming discovered a variable-length encoding for non-negative integers. The rule is as follows:

1. Write the given non-negative integer in binary. For example, $(0)_{10} = (0)_2$, and $(926)_{10} = (1110011110)_2$.
2. Split the binary number into groups of $7$ bits, from the least significant bit to the most significant bit, padding the highest group with leading zeros if it is shorter than $7$ bits. For example, $(0)_2$ becomes a single group 0000000; $(1110011110)_2$ becomes two groups 0011110 and 0000111.
3. Starting from the low-order group, prepend one most-significant bit to each group. If the group is the last group, prepend a 0; otherwise prepend a 1. Thus $0$ is encoded as 00000000 (one byte), and $926$ is encoded as 10011110 and 00000111 (two bytes).

This encoding uses fewer bytes for small numbers and can use many bytes for very large numbers. For example, the binary of $987654321012345678$ is $(0001101\ 1011010\ 0110110\ 1001011\ 1110100\ 0100110\ 1001000\ 0010110\ 1001110)_2$, so its variable-length encoding (written in hexadecimal) is CE 96 C8 A6 F4 CB B6 DA 0D, $9$ bytes in total.

Can you write a program that computes the variable-length encoding of a non-negative integer?

Input Format

The first line contains a single non-negative integer $N$. It is guaranteed that $0 \le N \le 10^{18}$.

Output Format

Output one line: for each byte of the variable-length encoding of $N$, print its value as a two-digit hexadecimal number (using uppercase letters A–F), with a single space between consecutive bytes.

Sample Input

Sample Input 1

0

Sample Input 2

926

Sample Input 3

987654321012345678

Sample Output

Sample Output 1

00

Sample Output 2

9E 07

Sample Output 3

CE 96 C8 A6 F4 CB B6 DA 0D

Sample Explanation

For input $0$, its binary is $0$, which is grouped by $7$ bits into 0000000. Since it is the last group, the most-significant bit is 0, giving 00000000. Its hexadecimal is 00, so we output 00.

Constraints

For all test data, $0 \le N \le 10^{18}$.