Xiaoqiang and Amoeba are good friends.

Amoeba has developed a high-end image recognition system and turned it into a mobile app. This recognition system has special capabilities; for example, it can recognize whether an image contains a cute puppy.

The app consists of two modules: a feature extraction module and a classification module. Whenever Xiaoqiang takes a picture, the feature extraction module extracts a 01-string of length $n$ and stores it. When Xiaoqiang wants to perform recognition, the classification module classifies based on the extracted 01-string (i.e., outputs an answer of 0 or 1).

To protect the classification algorithm, Amoeba's app is encrypted. After pestering Amoeba, Xiaoqiang figured out the working principle of the classification module.

The classification module recovers $m$ bits of "effective information" from the input $n$-bit 01-string. Each piece of "effective information" is the XOR sum of certain input variables. Afterward, the classification module uses this "effective information" to perform calculations to obtain the true result. For further encryption, Amoeba also adds "noise." "Noise" means that the classification module will intentionally flip the result according to a certain ratio. What Xiaoqiang gets might be the result after being flipped.

For example, the algorithm steps of the classification module might be as follows:

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 01-string, and $x[i]$ represents the $i$-th bit, which is a number that is either 0 or 1. $g(x[])$ is a function that returns 0 in most cases and occasionally returns 1. $h$ is a function related to $z[]$, and its return value is 0 or 1. $z[0], z[1], z[2]$ are the "effective information."

To prevent Xiaoqiang from seeing the algorithm from the app's source code, this algorithm has been obfuscated. For convenience, we call the obfuscated algorithm the "obfuscated algorithm." The code of the obfuscated algorithm has $Q$ lines, and each line looks like this:

$y[u] = (\text{not } (y[v] \text{ and } y[s])) \text{ xor } y[d] \text{ xor } y[e]$

Here, $y[]$ is a 01-array of length $L$; xor represents XOR, and represents AND, and not represents NOT. $u, v, s, d, e$ are the parameters of this line. Initially, $y[0] \sim y[n-1]$ contain the $n$ input bits $x[0] \sim x[n-1]$, and all other positions are 0. After executing these $Q$ lines of code, the bit $y[0]$ is the output.

Xiaoqiang is very angry about Amoeba's practice of encrypting at the cost of performance. Therefore, Xiaoqiang intends to crack Amoeba's classification algorithm from the obfuscated algorithm. For convenience, we call the cracked algorithm the "cracked algorithm." Xiaoqiang hopes you can help him crack:

1. How to extract the effective information. This can be expressed as $m$ subsets of $\{0, 1, \dots, n-1\}$, where each subset corresponds to which input bits are XORed to obtain an piece of effective information.
2. The function $h$ that maps these $m$ bits of effective information to the classification result. This function is represented by a lookup table of length $2^m$, where each bit is 0 or 1; these $2^m$ bits correspond to every possible situation of the $m$ bits of effective information.

Of course, this cracking algorithm is not unique; there may be multiple combinations of effective information extraction methods and lookup tables. You only need to provide one of them.

Amoeba guarantees that the introduced noise ratio does not exceed $p$. That is, the cracked algorithm you need to find and the obfuscated algorithm produce the same result on at least $2^n(1-p)$ different inputs; and Amoeba guarantees that such an algorithm exists.

At the same time, Amoeba also guarantees that these $m$ pieces of effective information are necessary, i.e., $h$ cannot be simplified into a function with fewer than $m$ inputs.

Input

The input file pdt.in represents an obfuscated algorithm. The first line of the input file contains 4 integers $n, m, L, Q$. The next $Q$ lines each contain 5 integers $u, v, s, d, e$, representing the parameters of each line.

Output

The output file pdt.out represents the cracked algorithm you provide. First, output $m$ lines, each containing an $n$-bit 01-string, representing which input bits are XORed to obtain each piece of effective information. Here, 1 indicates that the input bit is included, and 0 indicates it is not. Next, output a 01-string of length $2^m$, representing the lookup table for the function $h$. The items in the lookup table are arranged in lexicographical order. That is, first arrange the items where the first piece of effective information is 0, then those where the first piece is 1. When arranging the items where the first piece of effective information is 0, first arrange those where the second piece is 0, then those where the second piece is 1, and so on.

Examples

Input 1

3 2 4 1
0 1 2 2 2

Output 1

001
010
1110

Note 1

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]

Where $x[0..n-1]$ represents the 0-th to $(n-1)$-th bits of the 01-string $x$. In this code, the output corresponding to each input is as follows:

The sample output is a cracking scheme, equivalent to the following code:

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

The input and output of the $h$ function have the following correspondence:

It can be seen that for every input, the output of the cracked algorithm and the obfuscated algorithm are the same.

Input 2

See pdt/pdt.in and pdt/pdt.ans in the contestant directory.

Constraints

For 10% of the data, $m=1, p=0$; For another 30% of the data, $m=1$; For another 20% of the data, $m=2$; For another 20% of the data, $m=3$; For another 20% of the data, $m=4$. For all data, $1 \le n \le 64, 1 \le L \le 256, 1 \le Q \le 1024, 0 \le p \le 0.01, 0 \le u, v, s, d, e < L$ (Note: the value of $p$ is not given in the input file).

Note

Using bitwise operations to calculate function values on multiple inputs at once can greatly accelerate your program.