Підтікальна криптографія
Судді ACM ICPC дуже обережні, щоб не розкрити свої задачі, і всі комунікації зашифровані. Однак, іноді трапляються помилки, наприклад, використання занадто слабкої схеми шифрування. Ось приклад такої ситуації.
Обране шифрування було дуже простим: зашифрувати кожен рядок вхідних даних, перевертаючи деякі біти відповідно до спільного ключа. Щоб забезпечити розумну безпеку, розмір як рядка, так і ключа становить 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.
Виключне або - це логічний оператор, який дорівнює 1, коли тільки один з його операндів дорівнює 1, і 0 в іншому випадку. Ось його визначення для 1-бітних цілих чисел.
Як ви бачите, він ідентичний додаванню за модулем 2. Для двох 32-бітних цілих чисел a і b, їх побітове виключне або a ^ b визначається наступним чином, використовуючи їх двійкові представлення, що складаються з 0 і 1.
a ^ b = a[31] ... a[1] a[0]^b[31] ... b[1] b[0] = c[31] ... c[1]c[0]
де
Наприклад, використовуючи двійкову нотацію, 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] додається парну кількість разів, але найнижчий біт N9 ^ 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 0 1, то K[0] має бути 0.
Поки що все добре. Чи можете ви зробити краще?
Ви повинні знайти ключ, використаний для кодування.
Вхідні дані
Вхідні дані починаються з рядка, що містить лише додатне ціле число S, яке вказує на кількість наборів даних у вхідних даних. S не більше 1000.
Далі йдуть S наборів даних. Кожен набір даних складається з дев'яти 32-бітних цілих чисел, що відповідають першим дев'яти рядкам комунікації. Вони записані у шістнадцятковій нотації, використовуючи цифри від '0' до '9' та малі літери a до f, і без провідних нулів. Вони розділені пробілом або новим рядком. Кожен набір даних закінчується новим рядком.
Вихідні дані
Для кожного набору даних ви повинні вивести ключ, використаний для кодування. Кожен ключ має з'явитися окремо на своєму рядку і бути записаним у шістнадцятковій нотації, використовуючи цифри від '0' до '9' та малі літери a до f, і без провідних нулів.