Insecurity

Throughout the history of operating systems, security has always been a concern, and storing passwords safely has been studied for a long time. Passwords must not be stored in readable form, so today many systems store them as a hash (for example, an MD5 hash).

One attack against hash-based storage is to precompute the hashes of many commonly used passwords and compare them against the stored hashes. To counter this, a company claimed that encrypting the username and password together would be safe. That claim is weaker than it sounds. To demonstrate the weakness, you obtained from one of their servers a list of usernames, a list of passwords, and an encrypted string.

The encryption works as follows. Let $w$ be the word to be encrypted, with characters $w_0, w_1, \dots, w_{n-1}$; each character is represented by 8 bits using ordinary ASCII encoding. Let $c_i$ be the encryption of the first $i+1$ characters of $w$. Here $c_i$ is treated as a single bitstring, not as a sequence of characters. The rules are:

$c_0 = w_0$

$c_i = (c_{i-1} \ll 4) \oplus w_i \quad (i \ge 1)$

Here $\ll$ is a bitwise left shift. For example, the bitstring 00101011 becomes 0010101100 when shifted left by 2. During encryption the bitstring may keep growing and no bits are ever discarded. Zero bits matter, so even leading zero bits are never dropped; the effect of the shift is to append zero bits on the right.

The operator $\oplus$ is a bitwise XOR: it yields 0 when the two bits are equal and 1 otherwise. For example, 100011 XOR 0101 = 100110 (the shorter operand is right-aligned).

The word to be encrypted is the concatenation of the username and the password, that is, username + password.

The first line contains the number of test cases. Each test case has the following format:

• One line with the encrypted username and password that must be cracked. The bitstring is given in upper-case hexadecimal digits, with every 4 bits shown as one hexadecimal digit. For example, the bitstring 110010101101 is written as CAD.
• One line with $m$ ($1 \le m \le 10^5$), the number of users in the system.
• The next $m$ lines each contain one username.
• The next $m$ lines each contain one password.

Usernames and passwords contain only the following characters: a-z, A-Z, 0-9, and the special characters _ - = + ! @ # $ % { } & * ( ) [ ] \ | / < > , .. Each username and each password has length between 8 and 30, inclusive. The ASCII values of the characters are used during encryption.

All usernames are distinct, and all passwords are distinct.

For each test case, output the username and the password that were concatenated and encrypted to form the given input, on two separate lines: the username on the first line and the password on the second. The input is guaranteed to admit a unique solution for every test case.