ACM ICPC 加密通信分析

$ACM\ ICPC$评委非常小心，不泄露他们的问题，并且所有通信都经过加密。但是，有时确实会犯错误，例如使用太弱的加密方案。下面是一个例子。

选择的加密非常简单：通过根据共享密钥翻转一些位来加密输入的每个块。为了提供合理的安全性，$chunk$和$key$的大小均为$32$位。也就是说，假设输入是一个$m$个$32$位整数序列。

$N_1\ N_2\ N_3\ ...\ N_m$

使用键$K$编码后，它变为以下$m$个$32$位整数序列。

$(N_1∧K)\ (N_2∧K)\ (N_3∧K)\ ...\ (N_m∧K)$

其中$(a∧b)$是$a$和$b$的按位异$OR$。$Exclusive\ or$是逻辑运算符，当只有一个作数为$1$时为$1$，否则为$0$。这是它对$1$位整数的定义。

0 ♁ 0 = 0     0 ♁ 1 = 1
1 ♁ 0 = 1     1 ♁ 1 = 0

如您所见，它与加法模$2$相同。对于两个$32$位整数$a$和$b$，它们的按位互斥或$a ∧ b$使用由$0$和$1$组成的二进制表示形式定义如下。

$a ∧ b = a_{31}...a_1a_0 ∧ b_{31}...b_1b_0 = c_{31}...c_1c_0$

其中$c_i = a_i ♁ b_i$（$i = 0, 1, ..., 31$）。例如，使用二进制表示法$11010110 ∧ 01010101 = 10100011$或使用十六进制$d6 ∧ 55 = a3$。

由于这种加密对统计攻击的攻击是出了名的弱，因此必须提前压缩消息，使其没有统计规律性。我们假设$N_1\ N_2\ ...\ N_m$已经处于压缩状态。但是，问题在于压缩算法本身引入了某种形式的规律性：在每$8$个整数压缩数据之后，它会插入一个校验和，即这些整数的总和。也就是说，在上面的输入中，

$N_9 = N_1 + ... + N_8$

其中加法取模$2^{32}$。

幸运的是，您可以拦截法官之间的通信。也许它包含期末考试的问题！由于您非常聪明，您肯定已经看到您可以轻松找到密钥的最低位，用$K_0$表示。一方面，如果$K_0 = 1$，那么编码后，$Σ_{1<=i<=8}(N_i∧K)$的最低位保持不变，因为$K_0$增加了偶数次，但$N_9∧K$的最低位发生了变化，因此它们应该不同。另一方面，如果$K_0 = 0$，则编码后$Σ_{1<=i<=8}(N_i∧K)$的最低位仍应与$N_9∧K$的最低位相同，因为它们不会改变。例如，如果编码后的最低位是$1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1$，那么$K_0$必须是$1$，但如果它们是$1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 0$，则$K_0$必须为$0$。

目前为止，一切都好。你能做得更好吗？您应该找到用于编码的密钥。

输入格式

输入以仅包含正整数$S$的行开头，指示输入中的数据集数。$S$不超过$1000$。其次是$S$个数据集。每个数据集都由九个$32$位整数组成，对应于通信的前九个块。它们以十六进制表示法书写，使用数字'$0$'到'$9$'和小写字母'$a$'到'$f$'，没有前导零。它们之间用空格或换行符分隔。每个数据集都以换行符结尾。

输出格式

对于每个数据集，您应该输出用于编码的键。每个键应单独出现在其行中，并以十六进制表示法书写，使用数字'$0$'到'$9$'和小写字母'$a$'到'$f$'，没有前导$0$。

示例

输入数据1

8
1 1 1 1 1 1 1 1 8
3 2 3 2 3 2 3 2 6
3 4 4 7 7 b a 2 2e
e1 13 ce 28 ca 6 ab 46 a6d
b08 49e2 6128 f27 8cf2 bc50 7380 7fe1 723b
4eba eb4 a352 fd14 6ac1 eed1 dd06 bb83 392b
cef593c08 847e522f 74c02b9c 26f3a4e1 e2720a01 6fe66007
7a4e96ad 6ee5cef6 3853cd88
60202fb8 757d6d66 9c3a9525 fbcd7983 82b9571c ddc54bab 853e52da
22047c88 e5524401

输出数据1

0 2 61c649 24afc7f fff95c5 546991d 901c4a1 6

来源

$日本\ 2004$