4939. NP Transformation

单点时限: 1.0 sec

内存限制: 1024 MB

NP (Negation & Permutation) transformation of a list of bitsets is that you could swap any two bits or flip any bits in all bitsets. Give two lists of bitsets $A$ and $B$, where $B$ is transformed by $A$. Your task is to find an NP transformation that transforms $A$ to $B$.

输入格式

The first line consists of two integers — $n$ and $m$ ($1 \le n,m \le 1000$), denoting the number of bitsets and the length of bitsets.

In the following $n$ lines, each line consists of $m$ bits per line, denoting the list of bitsets $A$.

In the following $n$ lines, each line consists of $m$ bits per line, denoting the list of bitsets $B$.

The input is guaranteed that $B$ is NP transformed by $A$.

输出格式

The first line consists of $m$ integers, denoting the permutation of $A$.

The second line consists of $m$ bits, denoting the negation of $A$.

样例

Input
2 4
0000
0111
0101
1011
Output
2 3 4 1
0 1 0 1

提示

After the permutation ${2,3,4,1}$ of A, the bitset list is ${0000, 1110}$.

And then after the negation ${0,1,0,1}$ of A, the bitset list is ${0101, 1011}$.

138 人解决,164 人已尝试。

168 份提交通过,共有 474 份提交。

2.8 EMB 奖励。

创建: 1 年,6 月前.

修改: 1 年,6 月前.

最后提交: 12 月前.

来源: N/A

题目标签