← 返回题目列表

AtCoder · icpc2014autumn_b

B. 未知开关

中文机器翻译题面 查看原题

问题陈述

在ICPC(国际插头连接器公司)的总部大楼里,有$M$个灯泡,由$N$个开关控制。 每个灯泡都可以通过一个开关打开或关闭。 每个开关可以控制多个灯泡。 当您操作开关时,该开关控制的所有灯泡都会改变其状态。 您丢失了记录开关和灯泡对应关系的表,并且想要恢复它。

您决定通过以下步骤恢复通信。

  • 首先,每个开关都关闭,每个灯泡也关闭。
  • 您操作了一些由$S_1$ 表示的开关。
  • 您检查 $B_1$ 代表的灯泡的状态。
  • 您操作了一些由$S_2$ 表示的开关。
  • 您检查 $B_2$ 代表的灯泡的状态。
  • ...
  • 您操作了一些由 $S_Q$ 表示的开关。
  • 您检查 $B_Q$ 代表的灯泡的状态。

操作某些开关并检查灯泡的状态后,开关和灯泡的状态将被保留以供下次操作。

你能用你操作过的开关和检查过的灯泡状态的信息来恢复开关和灯泡的对应关系吗?


输入

输入由多个数据集组成。 数据集数量不超过$50$,文件大小不超过$10\mathrm{MB}$。 每个数据集的格式如下。

$N$ $M$ $Q$
$S_1$ $B_1$
:
:
$S_Q$ $B_Q$

每个数据集的第一行包含三个整数$N$ ($1 \le N \le 36$)、$M$ ($1 \le M \le 1{,}000$)、$Q$ ($0 \le Q \le 1{,}000$),分别表示开关数量、灯泡数量和操作数量。 以下 $Q$ 行描述了有关您已操作的开关和您已检查的灯泡状态的信息。 其中第 $i$ 包含两个字符串 $S_i$ 和 $B_i$,长度分别为 $N$ 和 $M$。 每个$S_i$表示您操作过的开关集合:$S_{ij}$要么是$0$,要么是$1$,分别表示第$j$个开关未被操作或操作。 每个$B_i$表示灯泡的状态:$B_{ij}$是$0$或$1$,分别表示第$j$个灯泡关闭或打开。

您可以假设开关和灯泡之间存在与给定信息一致的对应关系。

输入的结束由包含三个零的行表示。

输出

对于每个数据集,输出开关和灯泡之间的对应关系,该对应关系由以 $36$ 为基数的 $M$ 数字组成。 在该问题的 base-$36$ 系统中,值 $0$-$9$ 和 $10$-$35$ 由字符 ' 表示0'-'9' 和 'A'-'Z'分别。 对应关系的第$i$个字符表示控制第$i$个灯泡的开关的编号。 如果您无法确定哪个开关控制第 $i$ 个灯泡,请输出 '?' 作为第 $i$ 个字符而不是开关编号。


示例输入

3 10 3
000 0000000000
110 0000001111
101 1111111100
2 2 0
1 1 0
2 1 1
01 1
11 11 10
10000000000 10000000000
11000000000 01000000000
01100000000 00100000000
00110000000 00010000000
00011000000 00001000000
00001100000 00000100000
00000110000 00000010000
00000011000 00000001000
00000001100 00000000100
00000000110 00000000010
0 0 0

样本输入的输出

2222221100
??
0
1
0123456789A