Background

The testdata on Luogu is only for non-official communication and is not official testdata. Official judging link: https://www.cspro.org/.

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.

Problem Description

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.

Input Format

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.

Output Format

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.

81
8001240102030405
060708090af03c00
0102030405060708
090a0b0c0d0e0f01
0203040506070809
0a0b0c0d0e0f0102
030405060708090a
0b0c0d0e0f010203
0405060708090a0b
0c0d0e0fc603000d
78

0102030405060708
090a000102030405
060708090a0b0c0d
0e0f010203040506
0708090a0b0c0d0e
0f01020304050607
08090a0b0c0d0e0f
0102030405060708
090a0b0c0d0e0f0d
0e0f0d0e0f0d0e0f
0d0e0f0d0e0f0d0e
0f0d0e0f0d0e0f0d
0e0f0d0e0f0d0e0f
0d0e0f0d0e0f0d0e
0f0d0e0f0d0e0f0d
0e02030405060708

Hint

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