A-Link with Checksum_2025牛客国庆集训派对day8

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Link has invented an algorithm called CRC-LINK. In order to calculate CRC-LINK checksum of a datagram, let's assume the input byte array as $D$ and the CRC-LINK polynomial as $P$ ( $P=\text{0x04C11DB7}$ ), and follow the three steps below.

Treat each byte of the input byte array $D$ as an 8-bit binary number. Append 32 zero bits to the end of $D$ , creating an initial remainder $R$ .
Repeat the following step for times, where is the number of bits in .
- If the most significant bit of $R$ is 1, shift $R$ one bit to the left, then perform an XOR operation: XOR the most significant 32 bits of $R$ with the CRC-LINK polynomial $P$ .
- Otherwise, just shift $R$ one bit to the left.
The most significant 32 bits of $R$ is the CRC-LINK checksum of $D$ .

For example, if $D$ = {0x01, 0x02}, the CRC-LINK checksum can be calculated by:

00000001 00000010 00000000 00000000 00000000 00000000
(shift left for 7 bits)
10000001 00000000 00000000 00000000 00000000 00000000
(shift left for 1 bit, then xor P)
00000110 11000001 00011101 10110111 00000000 00000000
(shift left for 5 bits)
11011000 00100011 10110110 11100000 00000000 00000000
(shift left for 1 bit, then xor P)
10110100 10000110 01110000 01110111 00000000 00000000
(shift left for 1 bit, then xor P)
01101101 11001101 11111101 01011001 00000000 00000000
(shift left for 1 bit)
11011011 10011011 11111010 10110010 00000000 00000000
(since we have shifted 16 bits in total, the left 32 bits above is what we need)

Please note that CRC-LINK may be slightly different from CRC32.

For a datagram consisting of three parts: a header ( $n_1$ bytes), a checksum ( $4$ bytes), and a footer ( $n_2$ bytes), the header and footer are given, while the checksum needs to be determined by you. You should choose a checksum that matches the CRC-LINK calculation result of the entire datagram. Formally, you should make sure CRC-LINK(concat(header,YourAnswer,footer)) equals to YourAnswer.

You may refer the example explanation for better understanding of how to check your answer.

输入描述:

The first line contains two integers,  and  (), representing the lengths of the header and footer, respectively.

The second line contains  integers, where the -th integer  () represents the value of the -th byte in the header.

The third line contains  integers, where the -th integer  () represents the value of the -th byte in the footer.

输出描述:

If a feasible checksum exists, output the checksum value (in decimal). Otherwise, output `-1'.

If multiple feasible solutions exist, you can output any one of them.

示例1

输入

复制

1 2
114
51 4

输出

复制

456567105

说明

In the first example, when outputting `456567105', the answer is correct because CRC-LINK(72 1B 36 A9 41 33 04) equals to `456567105'.