P16669 [CSPro 30] Decompression.

The testdata on Luogu is only for non-official communication and is not official testdata. Official judging link: . Xixi Aifu Island Operations Company is a large enterprise responsible for maintaining and operating the island’s infrastructure. Within the company, many departments in charge of different businesses need to use server facilities. To make management easier and reduce operating costs, the company built a private cloud system. Besides providing hosted virtual machine services, this private cloud system also offers some other services. The most well-received one is the log service. Previously, logs of different business systems were stored separately on their own servers, which was not only inconvenient for viewing and analysis but also had the risk of loss. The log service can collect logs from different business systems in a unified way, making them easier to view and manage. The logs collected by the log server are plain text and highly structured. This means log data can be compressed very small. However, the amount of log data is huge and efficiency requirements are high, so it is acceptable to sacrifice some compression ratio and use an efficient compression algorithm to compress the log data. Little C is assigned to implement a program to decompress the logs. Given a segment of compressed log data, he needs to decompress it.

The data stream produced by this compression algorithm can be viewed as a sequence of elements. There are two kinds of elements: literals and back-references. A literal contains a sequence of bytes; when decompressing it, output these bytes directly. A back-reference repeats and outputs a part of the data stream that has already been decompressed. A back-reference can be written as $\langle o, l \rangle$, containing two numbers: the offset $o$ and the length $l$. The offset indicates how far to look back from the current position, and the length indicates how many bytes need to be output repeatedly. It is required that $o, l > 0$. If $p$ bytes have already been decompressed, then: - When $o \ge l$, it means to output the $l$ bytes starting from offset $(p - o)$ (the first byte has offset $0$). For example, if the already decompressed data stream is `abcde`, then the back-reference $\langle 3, 2 \rangle$ means output `cd`. - When $o < l$, it means to first output the $o$ bytes starting from offset $(p - o)$, then keep outputting these $o$ bytes repeatedly until a total of $l$ bytes have been output. For example, if the already decompressed data stream is `abcde`, then the back-reference $\langle 2, 5 \rangle$ means output `deded`. The compressed data format consists of two parts: the header field and the data field. The header field stores the length of the original data. Let the original data length be $n$. Then $n$ can be expressed as $\sum_{k=0}^{d} c_k \times 128^k$, where $0 \le c_k < 128$ and $c_d \ne 0$. The header field has length $(d + 1)$ bytes, storing in order $c_0 + 128, c_1 + 128, \cdots, c_{d-1} + 128, c_d$. That is, each byte uses the lower $7$ bits to store $c_k$. The highest bit is $0$ for the last byte, and $1$ for all other bytes. For example, if the original data length is $1324$, then $c_k$ are $44, 10$, i.e. `0x2C`, `0x0A` in hexadecimal. Therefore, the header field length is $2$, and the byte sequence is `0xAC 0x0A`. :::align{center}  ::: The data field stores the compressed data, which is a contiguous sequence of elements. The lowest two bits of the first byte of each element indicate the element type. When the lowest two bits are $0$, it is a literal. If the literal contains $l$ bytes and $l \le 60$, then the upper $6$ bits of the first byte represent $(l - 1)$. The following $l$ bytes are the original bytes contained in the literal. For example, byte `0xE8` is binary `1110 1000`. The lowest two bits are $0$, so it is a literal. The upper six bits are `111010`, which is $58$, meaning the literal contains $59$ bytes. Therefore, the following $59$ bytes are the original bytes contained in this literal. If $l > 60$, then represent $(l - 1)$ in $1$ to $4$ bytes in little-endian order, and store them after the first byte. When the value stored in the upper six bits of the first byte is $60, 61, 62$, or $63$, it means that $(l - 1)$ is stored using $1, 2, 3$, or $4$ bytes, respectively. For example, in the byte sequence `0xF4 0x01 0x0A`, the first byte is binary `1111 0100`. The lowest two bits are $0$, so it is a literal. The upper $6$ bits are `111101`, which is $61$, meaning the next two bytes store the literal length. The following two bytes `0x01 0x0A`, in little-endian order, form the hexadecimal number `0x0A01`, i.e. decimal $2561$, meaning this literal contains $2562$ bytes. The following $2562$ bytes are the original bytes contained in this literal. :::align{center}   ::: When the lowest two bits of the first byte are `01`, it is a back-reference $\langle o, l \rangle$, with $4 \le l \le 11$ and $0 < o \le 2047$. Here, $o$ takes $11$ bits: its lower $8$ bits are stored in the following byte, and its upper $3$ bits are stored in the upper $3$ bits of the first byte. $(l - 4)$ takes $3$ bits, stored in bits $2$ to $4$ of the first byte, as shown below. ``` 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 +-----+-----+-+-+ +----------------+ |o(h3)| l-4 |0|1| |o (lower 8 bits)| +-----+-----+-+-+ +----------------+ ``` For example, bytes `0x2D 0x1A` have first byte binary `001 011 01`. The lowest two bits are `01`, so it is a back-reference. Bits $2$ to $4$ are `011`, which is $3$, meaning $(l - 4) = 3$, so $l = 7$. The upper $3$ bits are `001`; together with the following byte `0x1A`, they form the hexadecimal number `0x11A`, i.e. decimal $282$, meaning $o = 282$. Therefore, this back-reference is $\langle 282, 7 \rangle$. :::align{center}  ::: When the lowest two bits of the first byte are `10`, it is a back-reference $\langle o, l \rangle$, with $1 \le l \le 64$ and $0 < o \le 65535$. Here, $o$ takes $16$ bits and is stored in little-endian order in the following two bytes. $(l - 1)$ takes $6$ bits and is stored in the upper $6$ bits of the first byte. For example, bytes `0x3E 0x1A 0x01` have first byte binary `0011 1110`. The lowest two bits are `10`, so it is a back-reference. The upper $6$ bits are `001111`, which is $15$, meaning $(l - 1) = 15$, so $l = 16$. The following two bytes `0x1A 0x01`, in little-endian order, form the hexadecimal number `0x011A`, i.e. decimal $282$, meaning $o = 282$. Therefore, this back-reference is $\langle 282, 16 \rangle$. :::align{center}  ::: We规定 that the lowest two bits of an element’s first byte are not allowed to be `11`. If this happens, then the data field is invalid. The compressed data is valid if and only if all of the following conditions are satisfied. 1. The header field length does not exceed $4$ bytes. 2. The header field can be correctly restored to the original data length. 3. The lowest two bits of the first byte of each element are not `11`. 4. Each element can be restored to the original data according to the rules. 5. The obtained original data length is exactly equal to the original data length encoded in the header field.

Read input from standard input. The input contains multiple lines. The first line is a positive integer $s$, indicating the number of bytes of the compressed data to be decompressed. Next, there are $\left\lceil \frac{s}{8} \right\rceil$ lines describing the compressed data. Each line contains only digits or letters `a` to `f`. Every two characters form a hexadecimal number representing one byte. Except for the last line, each line contains exactly $8$ bytes. The input data is guaranteed to be valid.

Write output to standard output. Output the decompressed data. Output $8$ consecutive bytes per line, and each byte is represented by two hexadecimal digits (digits or letters `a` to `f`). The last line may contain fewer than $8$ bytes.

### Explanation for Sample 1 The above input data can be reorganized as. ``` 80 01 24 0102030405060708090a f0 3c 000102030405060708090a0b0c0d0e0f 0102030405060708090a0b0c0d0e0f 0102030405060708090a0b0c0d0e0f 0102030405060708090a0b0c0d0e0f c6 0300 0d 78 ``` First read the first byte `80`. Its highest bit is $1$, so continue reading the second byte `01`. Its highest bit is $0$, so reading the header field ends. We get $c_0 = 0, c_1 = 1$, and the original data length is. $$ \begin{aligned} & 0 \times 128^0 + 1 \times 128^1 \\ = & \ 128. \end{aligned} $$ Then continue reading byte `24`, whose binary is `0010 0100`. The lowest two bits are `00`, so it is a literal. Taking its upper six bits gives decimal $9$, meaning the length of this literal is $10$. Then read $10$ bytes to get the literal `0102030405060708090a`. Then continue reading byte `f0`, whose binary is `1111 0000`. The lowest two bits are `00`, so it is a literal. Taking its upper six bits gives decimal $60$, meaning the next one byte is the literal length minus $1$. Continue reading byte `3c` to get the number $60$, meaning this literal has length $61$, and then read $61$ bytes. Then continue reading byte `c6`, whose binary is `1100 0110`. The lowest two bits are `10`, so it is a back-reference. Taking its upper six bits gives decimal $49$, meaning the back-reference length $l$ is $50$. Then read two bytes `03 00`, which in little-endian order form the hexadecimal number `0x0003`, i.e. decimal $3$, meaning the back-reference offset $o$ is $3$. Therefore, this back-reference is $\langle 3, 50 \rangle$. Since $50 = 16 \times 3 + 2$, repeat the last three bytes in the buffer `0d 0e 0f` for $16$ times, then output `0d 0e` to make a total of $50$ bytes. Then continue reading byte `0d`, whose binary is `0000 1101`. The lowest two bits are `01`, so it is a back-reference. Take bits $2$ to $4$, which are `011`, i.e. decimal $3$, meaning the back-reference length $l$ is $7$. Then read one byte `78`, whose binary is `0111 1000`. Combine it with the top three bits `000` of this element’s first byte `0d` to get `000 0111 1000`, which is decimal $120$, meaning the back-reference offset $o$ is $120$. Therefore, this back-reference is $\langle 120, 7 \rangle$. Previously, $121$ bytes have been output. Now output $7$ bytes starting from position with offset $121 - 120 = 1$ from the beginning of the buffer, i.e. `02030405060708`. At this point, the input has been fully processed. A total of $10 + 61 + 50 + 7 = 128$ bytes have been output, consistent with the original data length read from the header field, so decompression succeeds. ### Subtasks - For $10\%$ of the input, the decompressed data length does not exceed $127$ bytes, and contains only literals, and the length of data in each literal element does not exceed $60$ bytes. - For $20\%$ of the input, the decompressed data length does not exceed $1024$ bytes, and contains only literals, and the length of data in each literal element does not exceed $60$ bytes. - For $40\%$ of the input, the decompressed data length does not exceed $1024$ bytes, and contains only literals. - For $60\%$ of the input, the decompressed data length does not exceed $1024$ bytes, and all back-references have first bytes whose lowest two bits are `01`. - For $80\%$ of the input, the decompressed data length does not exceed $4096$ bytes. - For $100\%$ of the input, the decompressed data length does not exceed $2\text{MiB}$ ($2 \times 2^{20}$ bytes), and $s \le 2 \times 10^6$, and the data is guaranteed to be valid compressed data. Translated by ChatGPT 5