题目描述

小强和阿米巴是好朋友。

阿米巴研发出了一套相当高端的图片识别系统，并把它写成了一个手机app。这个识别系统具备特殊的识别能力，比如说，它能够识别一张图片里是否有萌萌的小狗。

这个app由两个模块组成，特征提取模块和分类模块。每当小强拍摄一张图片，特征提取模块就从中提取出一个长度为 \(n\) 的 01 串并存储起来。当小强希望进行识别的时候，分类模块就会根据提取出的 01 串进行分类（即，输出一个 \(0\) 或者 \(1\) 的答案）。

为了保护分类算法，阿米巴的这个 app 是经过加密处理的。经过对阿米巴的死缠烂打，小强弄明白了这个分类算法的工作原理。

分类模块会从输入的这个 \(n\) 位 01 串中恢复出 \(m\) 位的“有效信息”。每个“有效信息” 都是经过某些输入变量的异或。之后，分类模块会利用这些 “有效信息” 进行运算来得到真正的结果。为了进一步加密，阿米巴还会加入 “噪声”。所谓 “噪声”，是指这个分类模块会故意按一定的比例将结果反转。小强拿到的可能是经过了反转的结果。

举个例子，分类模块的算法步骤可能是这样的：

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[])

其中 x[] 是一个 01 串，x[i] 表示其中的第 \(i\) 位，即一个 \(0\) 或 \(1\) 的函数。

g(x[]) 是某个在大多数情况下返回 \(0\)，偶尔返回 \(1\) 的函数。\(h\) 是某个关于 z[] 的函数，其返回值为 \(0\) 或 \(1\)。

z[0], z[1], z[2] 就是 “有效信息”。

为了让小强无法从app中看出算法，这个算法被进行了混淆。为了方便起见，我们把混淆之后的算法叫做“混淆版算法”。混淆版算法的代码共有 \(Q\) 行，它的每一行都是这个样子：

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

其中 y[] 是一个长度为 \(L\) 的 01 数组；xor 表示异或，and 表示与，not 表示非。\(u, v, s, d, e\) 是这一行的参数。初始的时候，y[0]～y[n - 1] 里面放置了 x[0]～x[n - 1] 这 \(n\) 个输入位，其他地方都是 \(0\)。执行完这 \(Q\) 行代码之后，y[0] 这个位就是输出。

对于阿米巴的这种以损失性能为代价进行加密的行径，小强感到很愤怒。于是，小强打算从混淆版算法中破解出阿米巴的分类算法。为了方便起见，我们把破解得到的算法叫做“破解版算法”。小强希望你能够帮他破解出：

如何提取有效信息。这个可以表述为 \(m\) 个 \(\{0, 1, \dots, n - 1\}\) 的子集，每个子集对应了一个有效信息是从哪几个输入位异或得到的；

把这 \(m\) 位有效信息映射到分类结果上的函数 \(h\)。该函数用一个长度为 \(2^m\)，每一位均为 \(0\) 或 \(1\) 的查找表表示；这 \(2^m\) 位分别对应了 \(m\) 位有效信息每一种可能的情况。

当然，这种破解算法是不唯一的，即，可能会有多种有效信息提取方法和查找表的组合。你只需要给出其中的一种即可。

阿米巴保证，引入的噪声比例不超过 \(p\)。即，你需要求出的破解版算法，和混淆版算法至少在 \(2^n(1 - p)\) 个不同输入上得到的结果是一样的；并且阿米巴保证这样的算法是存在的。

同时，阿米巴也保证，这 \(m\) 个有效信息都是必须的，即，\(h\) 无法化简为少于 \(m\) 个输入的函数。

输入

第一行，包含 \(4\) 个整数 \(n,m,L,Q\)。

接下来 \(Q\) 行，每行包含 \(5\) 个整数 \(u,v,s,d,e\)，表示每行的参数。

输出

先输出 \(m\) 行，每行包含 \(1\) 个 \(n\) 位 \(01\) 串，表示每个有效信息是由哪些输入位异或得到的。其中，\(1\) 表示包含该输入位，\(0\) 表示不包含。

接下来输出一行一个长度为 \(2^m\) 的 \(01\) 串，表示 \(h\) 函数的查找表。查找表中的项按字典序进行排列。即，先排第一个有效信息是 \(0\) 的，再排第一个有效信息是 \(1\) 的。排第一个有效信息是 \(0\) 的项的时候，先排第二个有效信息是 \(0\) 的，再排第二个有效信息是 \(1\) 的。以此类推。

样例 1

输入

3 2 4 1
0 1 2 2 2

输出

001
010
1110

解释

样例输入等价于如下代码

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]

其中 x[0..n-1] 表示 01 串 \(x\) 的第 \(0\) 位到第 \(n - 1\) 位。

在这段代码中，每一种输入对应的输出如下：

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

样例输出是一种破解方案，等价于如下代码：

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

\(h\) 函数的输入和输出有如下对应关系：

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

可以发现，对于每一种输入，破解版算法和混淆版算法的输出是相同的。

数据范围限制

对于 \(10\%\) 的数据，\(m=1\)，\(p=0\)；

对于另外 \(30\%\) 的数据，\(m=1\)；

对于另外 \(20\%\) 的数据，\(m=2\)；

对于另外 \(20\%\) 的数据，\(m=3\)；

对于另外 \(20\%\) 的数据，\(m=4\)。

对于所有的数据, \(1 \leq n \leq 64\),\(1 \leq L \leq 256\),\(1 \leq Q \leq 1024\),\(0 \leq p \leq 0.01\),\(0 \leq u,v,s,d,e < L\)（注意，输入中并没有把 \(p\) 的值给你）。

提示

使用位运算一次在多个输入上求出函数值可以极大的加速你的程序。

来源

WC2015