{"extraResources":{"example.01.mu":"TVXzATExMjAyNQ0K","example.02.mu":"TVXzATEyOA0K","example.05.mu":"TVXzATE2Mzg0DQo=","example.06.mu":"TVXzATIxNDc0ODM2NDcNCg==","example.04.mu":"TVXzATQyDQo=","example.03.mu":"TVXzATANCg=="},"scoring":null,"notes":"","legend":"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.\r\n\r\nTo 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 \\textit{big-endian}, meaning that $b_1$ contains the most significant bits of the encoded value.\r\n\r\nFor example, here's how to find the compact representation of $n = 112025$. First, we find its binary representation:\r\n\\begin{center}\r\n$112025 = 11011010110011001_2$\r\n\\end{center}\r\n\r\nNext, we split it into 7-bit chunks, padding with zeros on the left if necessary:\r\n\\begin{center}\r\n$0000110$ / $1101011$ / $0011001$\r\n\\end{center}\r\n\r\nThe 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:\r\n\\begin{center}\r\n\\begin{tabular}{l}\r\n$b_1 = 10000110_2 = 134$\\\\\r\n\r\n$b_2 = 11101011_2 = 235$\\\\\r\n\r\n$b_3 = 00011001_2 = 25$\\\\\r\n\\end{tabular}\r\n\\end{center}\r\n\r\nYou are given an integer $n$, and your task is to find its compact representation.\r\n\r\n","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"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$.","inputFile":"stdin","outputFile":"stdout","input":"The only line contains a single integer $n$ ($0 \\le n \\le 2^{31}-1$).","authorName":"Gennady Korotkevich","sampleTests":[{"output":"134 235 25\r\n","input":"112025\r\n","inputFile":"example.01","outputFile":"example.01.a"},{"output":"129 0\r\n","input":"128\r\n","inputFile":"example.02","outputFile":"example.02.a"},{"output":"0\r\n","input":"0\r\n","inputFile":"example.03","outputFile":"example.03.a"},{"output":"42\r\n","input":"42\r\n","inputFile":"example.04","outputFile":"example.04.a"},{"output":"129 128 0\r\n","input":"16384\r\n","inputFile":"example.05","outputFile":"example.05.a"},{"output":"135 255 255 255 127\r\n","input":"2147483647\r\n","inputFile":"example.06","outputFile":"example.06.a"}],"name":"Compact Encoding","interaction":null,"memoryLimit":1073741824,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Дмитрий Штукенберг\\\\\r\n         Разработка: & Дмитрий Штукенберг\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nВ задаче (если опустить подробности) требуется преобразовать значение в 128-ричную систему счисления (7 битов как раз образуют одну 128-ричную цифру). \r\n\r\nЭто можно сделать стандартным образом, через печать остатков от последовательного деления на 128, но с двумя отличиями:\r\n\\begin{enumerate}\r\n\\item Ко всем результатам, кроме самого первого (младшие 7 бит), нужно прибавить 128. \r\n\\item Порядок байтов от старшего к младшему (``big-endian'') требует в какой-то момент развернуть результат в обратном порядке (первый полученный остаток должен быть напечатан последним). Это можно сделать через векторы, а можно на уровне арифметики: сперва стандартным образом вычислим длину 128-ричного представления числа, а затем будем печатать отдельные значения в нужном порядке, тогда значение в 128-ричном разряде $k$ будет равно $\\lfloor \\frac{n}{2^{7k}} \\rfloor\\ \\text{mod}\\ 128$.\r\n\\end{enumerate}\r\n\r\nУмножение и деление в данной задаче удобно производить с помощью битовых сдвигов, а взятие остатка от деления --- через побитовую конъюнкцию."}