← 返回题目列表

Codeforces · 1275/E3

E3. 校验和

中文机器翻译题面 查看原题

VKontakte 用户数据存储在数万台服务器上。为了能够在将数据写入磁盘时检测错误,当前的 CRC32 校验和(Wiki、IEEE 802-3)会定期写入磁盘。得益于此,在读取数据时,您可以重新计算校验和并检查数据和校验和是否正确写入。

当然,大多数 VKontakte 服务都内置了校验和匹配检查。但有一天,事实证明,在一个数据段中,您需要将四个连续字节的值更改为新的值 - 您需要将序列 $$$a_i, a_{i+1}, a_{i+2}, a_{i+3}$$$ 的值替换为 $$$x_0, x_1, x_2, x_3$$$。同时,CRC32校验和的值必须保持不变。当然,如果序列改变了,它的校验和也会改变,所以除了把这四个字节改成新值之外,还选择了$$$a_{j},a_{j+1},a_{j+2},a_{j+3}$$$这四个字节,可以赋任意值。你的任务是为它们选择新的值,使得给定序列的CRC32不会改变,或者确定这是不可能的。由于更改数据是一项严肃的操作,因此在更改本身之前,您需要确定 $$$q$$$ 独立测试用例的序列将如何更改。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ — 文件中的字节数和需要解决问题的查询数 ($$$8 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$)。

第二行包含 $$$n$$$ 数字 $$$a_0, a_1, \ldots, a_{n-1}$$$ - 文件内容(以字节为单位)($$$0 \le a_i \le 255$$$)。

以下 $$$q$$$ 行包含六个数字,每个数字 $$$i, j, x_0, x_1, x_2, x_3$$$ - 位置 $$$i$$$,从这里开始,您需要用 $$$x_0, x_1, x_2, x_3$$$ 替换四个字节,从位置 $$$j$$$ 开始,您可以根据需要更改四个字节($$$0 \le i, j \le n-4$$$; $$$0 \le x_0, x_1, x_2, x_3 \le 255$$$)。保证段 $$$[i; i+3]$$$ 和 $$$[j; j+3]$$$ 不相交。

输出

对于每个请求,打印四个整数 $$$z_0, z_1, z_2, z_3$$$,需要用数字 $$$j, j+1, j+2, j+3$$$ 替换四个字节,这样 crc32 就不会改变。请注意,所有查询都是独立的,并且顺序实际上并没有改变。

如果有多个解决方案,则打印任意一个,如果此查询没有有效的解决方案,则打印无解决方案。

示例

输入 #1

8 1
1 2 3 4 5 6 7 8
0 4 0 0 0 0

输出 #1

212 34 127 159

输入 #2

16 3
4 5 6 7 0 0 0 0 0 0 0 85 200 47 47 0
11 0 0 0 0 0
3 12 7 0 0 0
0 11 0 0 0 0

输出 #2

0 0 0 0
200 47 47 0
0 0 0 0

注意

第一个示例中的字节序列 (1 2 3 4 5 6 7 8) 的 CRC32 等于 3fca88c5,修改后的序列 (0 0 0 0 212 34 127 159) 的 CRC32 也等于 3fca88c5。大多数 Linux 发行版中的标准 crc32 实用程序应该从中计算此校验和。

第二个示例中的序列的 CRC32 是 ecbb4b55。