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=16, q=8$$$ 的测试,您可以从此链接下载该测试。您的解决方案不需要通过该条件下的测试,也不会针对它们进行测试。如果您想使用条件中的测试来测试您的解决方案,请将其提交到任务 E3,其中前两个测试对应于条件中的示例。
输入
第一行包含两个整数 $$$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。