35020번 - Compact Encoding 다국어

문제

Binary formats often use compact representations for integers. Consider writing a 32-bit unsigned integer to a file: you must always reserve 4 bytes to represent it (remember, 8 bits make one byte). However, in many real-life applications, integer values tend to be small. Writing these small values using a fixed 4-byte representation results in files that are mostly filled with zero bytes.

To make the representation more compact, we introduce the following encoding scheme. Each value is represented as a sequence of bytes $b_1, b_2, \ldots, b_k,ドル where each $b_i$ is an integer between 0ドル$ and 255ドル,ドル inclusive. The most significant bit of each byte serves as a continuation flag, and the lower 7ドル$ bits carry the actual data. If the continuation flag is 1ドル,ドル more bytes follow; for the last byte, it is 0ドル$. The representation is big-endian, meaning that $b_1$ contains the most significant bits of the encoded value.

For example, here's how to find the compact representation of $n = 112025$. First, we find its binary representation:

112025ドル = 11011010110011001_2$

Next, we split it into 7-bit chunks, padding with zeros on the left if necessary:

0000110ドル$ / 1101011ドル$ / 0011001ドル$

The first two chunks have a following chunk, so the corresponding bytes have their most significant bit set to 1ドル$. The last chunk has no following chunk, so its most significant bit is 0ドル$. This gives us:

$b_1 = 10000110_2 = 134$

$b_2 = 11101011_2 = 235$

$b_3 = 00011001_2 = 25$

You are given an integer $n,ドル and your task is to find its compact representation.

입력

The only line contains a single integer $n$ (0ドル \le n \le 2^{31}-1$).

출력

Print a sequence of integers between 0ドル$ and 255ドル,ドル inclusive, representing the compact encoding of $n$. The encoding must not contain leading bytes with zero data bits: that is, it may not start with 128ドル$.

제한

노트