Description

Xiaoqiang and Amiba are good friends.

Amiba developed a fairly advanced image recognition system and released it as a mobile app. This recognition system has special capabilities; for example, it can recognize whether there is a cute puppy in a picture.

The app consists of two modules: a feature extraction module and a classification module. Every time Xiaoqiang takes a photo, the feature extraction module extracts a length-$n$ binary string and stores it. When Xiaoqiang wants a recognition result, the classification module classifies based on the extracted binary string (i.e., outputs either $0$ or $1$).

To protect the classification algorithm, Amiba encrypted the app. After much pestering, Xiaoqiang figured out how the classification algorithm works.

The classification module recovers $m$ bits of “effective information” from the $n$-bit input binary string. Each “effective information” bit is the XOR of some input variables. Then, the classification module uses these “effective information” bits to compute the final result. To further obfuscate, Amiba also adds “noise”, meaning the module intentionally flips the result with a certain probability. The result Xiaoqiang gets may be flipped.

For example, the steps of the classification module could be:

function f(x[]):
    z[0] = x[0] xor x[4] xor x[7]
    z[1] = x[12] xor x[2]
    z[2] = x[0] xor x[1] xor x[2] xor x[3]
    result = h(z[])
    return result xor g(x[])

Here x[] is a binary string, and x[i] denotes its $i$-th bit, i.e., either $0$ or $1$.

g(x[]) is a function that returns $0$ in most cases and occasionally returns $1$. $h$ is some function of z[] whose return value is $0$ or $1$.

z[0], z[1], z[2] are the “effective information”.

To prevent Xiaoqiang from seeing the algorithm directly in the app, the algorithm was obfuscated. For convenience, we call the obfuscated algorithm the “obfuscated version”. The obfuscated version has $Q$ lines of code, each of the form:

y[u] = (not (y[v] and y[s])) xor y[d] xor y[e]

Here y[] is a length-$L$ binary array; xor means XOR, and means AND, and not means NOT. $u, v, s, d, e$ are the parameters on that line. Initially, y[0] through y[n - 1] hold x[0] through x[n - 1], and all other positions are $0$. After executing these $Q$ lines, y[0] is the output.

Angered by Amiba’s practice of trading performance for encryption, Xiaoqiang decides to recover the classification algorithm from the obfuscated version. For convenience, we call the recovered algorithm the “cracked version”. Xiaoqiang hopes you can help him recover:

• How to extract the effective information. This can be represented as $m$ subsets of $\{0, 1, \dots, n - 1\}$, where each subset indicates which input bits are XORed to produce one effective information bit.
• The function $h$ mapping these $m$ effective information bits to the classification result. This function is represented by a lookup table of length $2^m$ whose entries are $0$ or $1$. These $2^m$ entries correspond to all possible values of the $m$ effective information bits.

Of course, the recovered algorithm is not unique; multiple combinations of effective information extraction and lookup tables may work. You only need to provide one.

Amiba guarantees that the noise rate is at most $p$. That is, your cracked version and the obfuscated version must agree on at least $2^n (1 - p)$ different inputs, and Amiba guarantees such an algorithm exists.

Amiba also guarantees that all $m$ effective information bits are necessary, i.e., $h$ cannot be simplified to a function of fewer than $m$ inputs.

Input Format

The first line contains 4 integers $n, m, L, Q$.

Then follow $Q$ lines, each containing 5 integers $u, v, s, d, e$, giving the parameters of each line.

Output Format

First output $m$ lines, each containing an $n$-bit binary string that indicates which input bits are XORed to produce each effective information bit. A 1 means the input bit is included; a 0 means it is not included.

Then output one line containing a binary string of length $2^m$ representing the lookup table of the function $h$. The entries are listed in lexicographic order: first list entries where the first effective information bit is $0$, then where it is $1$. While listing entries where the first effective information bit is $0$, first list those where the second effective information bit is $0$, then where it is $1$, and so on.

3 2 4 1
0 1 2 2 2

001
010
1110

Hint

[Sample explanation]

The sample input is equivalent to the following code:

y[] = 0000
input x[0..n-1]
y[0..n-1] = x[0..n-1]
y[0] = (not (y[1] and y[2])) xor y[2] xor y[2]
output y[0]

Here x[0..n-1] denotes bits $0$ through $n - 1$ of the binary string $x$.

In this code, the output for each input is:

input    000    001    010    011    100    101    110    111
output   1      1      1      0      1      1      1      0

A sample cracked solution is equivalent to:

input x[0..n-1]
z[0] = x[2]
z[1] = x[1]
output h(z[])

The inputs and outputs of the function $h$ are:

z[]       00    01    10    11
h(z[])    1     1     1     0

You can verify that for every input, the cracked version and the obfuscated version produce the same output.

Constraints

• For 10% of the testdata, $m = 1$, $p = 0$.
• For another 30% of the testdata, $m = 1$.
• For another 20% of the testdata, $m = 2$.
• For another 20% of the testdata, $m = 3$.
• For another 20% of the testdata, $m = 4$.
• For all testdata, $1 \leq n \leq 64$, $1 \leq L \leq 256$, $1 \leq Q \leq 1024$, $0 \leq p \leq 0.01$, and $0 \leq u, v, s, d, e < L$ (note that the value of $p$ is not provided in the input).

Tip

Using bitwise operations to evaluate the function on many inputs at once can greatly speed up your program.

Translated by ChatGPT 5