I1. Insecure
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The RXA cryptosystem is the same in both problems. Skip to paragraph beginning with "Cindy" for the difference between the two problems.

Alice and Bob were attending a cryptography seminar in the province of Siquijor, where they learned about the famous RSA cryptosystem used for public-key encryption. Inspired by this, they decided to create their own cryptosystem which they called RXA.

Suppose Alice wants to send Bob a secret message $$$M$$$, which is a string. They have developed the following three-pass protocol.

First, Alice encodes the string $$$M$$$ into a (possibly very large) integer $$$m$$$ (by a process described below). Now, she communicates this integer $$$m$$$ to Bob by the following procedure.

Let $$$a \oplus b$$$ denote the bitwise XOR of two non-negative integers $$$a$$$ and $$$b$$$ (see Notes for an explanation).

  • Alice generates a secret non-negative integer $$$a$$$, then sends to Bob the value $$$x := a \oplus m$$$.
  • Bob also generates a secret non-negative integer $$$b$$$, and sends back to Alice the value $$$y := b \oplus x$$$.
  • Alice then sends back to Bob the value $$$z := a \oplus y$$$.
From here, we can show that Bob can retrieve the integer $$$m$$$, since $$$m = b \oplus z$$$. Since Bob also knows the encoding scheme, he can then retrieve the original string $$$M$$$.

Note that the only values that can be heard by the public are $$$x$$$, $$$y$$$, and $$$z$$$. The secret integers $$$a$$$ and $$$b$$$ are not revealed by Alice and Bob, not even to each other.

Cindy calls them both idiots, because this cryptographic scheme has a fatal flaw. The message $$$M$$$ can actually be retrieved by a malicious third party! Let's prove it. Given $$$n$$$ (the length of the message), and $$$x$$$, $$$y$$$, and $$$z$$$ (the values broadcasted to the public), see if you can recover the secret message $$$M$$$ that Alice wanted to secretly share to Bob.

The encopding process from $$$M$$$ to $$$m$$$ is as follows. Replace each character of $$$M$$$ with a $$$5$$$-bit string as follows:

  • a becomes 00000
  • b becomes 00001
  • c becomes 00010
  • d becomes 00011
  • e becomes 00100
  • f becomes 00101
  • $$$\vdots$$$
  • y becomes 11000
  • z becomes 11001
  • _ becomes 11010
  • . becomes 11011
  • ? becomes 11100
  • ! becomes 11101
  • - becomes 11110
  • , becomes 11111
Let $$$|M|$$$ be the length of the message $$$M$$$. This should result in a binary string of length $$$5|M|$$$, which we interpret as the binary representation of some integer, and that integer is $$$m$$$.
Input

The first line of input contains a single integer $$$T$$$, denoting the number of test cases. The descriptions of $$$T$$$ test cases follow.

Each test case consists of a single line containing the four space-separated integers $$$|M|$$$, $$$x$$$, $$$y$$$, and $$$z$$$.

Output

For each test case, output one line containing a single string, denoting the answer for that test case.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq T \leq 10^4 \\ 1 \leq |M| \leq 25 \\ 0 \leq x, y, z \lt 32^{|M|} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{75} & |M| \le 6 \\ \hline 2 & \mathbf{20} & |M| \leq 12 \\ \hline 3 & \mathbf{5} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Note that $$$x$$$, $$$y$$$, and $$$z$$$ can be quite large... beware integer overflow.

Examples
Input
2
11 1669541533645137 9059692270620735 1841376433034227
8 940952787971 700576436 700511868052
Output
i_love_you!
password
Input
2
18 201191772701226744980892017 470232750687508483322404997 1012763572942237404468826031
21 23476430646951893696212210100392 23476510470843452443909826453115 23476551580580358895321272467822
Output
the_world_wonders.
squawk_chirp_quack!!!
Note

The logical XOR accepts two values as input, each $$$0$$$ or $$$1$$$. It returns $$$1$$$ if the two inputs are different, and returns $$$0$$$ if the two inputs are the same.

The bitwise XOR between two non-negative integers is computed by writing both inputs in binary (using the same number of bits, adding padding leading zeros if necessary), and then performing a logical XOR on each corresponding pair of bits at the same place values. For example, $$$5 \oplus 9 = 12$$$. We write $$$5 = 0101_2$$$ and $$$9 = 1001_2$$$, then: 


0101
1001
====
1100
and $$$1100_2 = 12$$$.