Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

blockquote {
  font-family: Menlo, Monaco, "Courier New", monospace;
  color: #333333;
  display: block;
  padding: 8.5px;
  margin: 0 0 9px;
  font-size: 12px;
  line-height: 18px;
  background-color: #f5f5f5;
  border: 1px solid #ccc;
  border: 1px solid rgba(0, 0, 0, 0.15);
  -webkit-border-radius: 4px;
  -moz-border-radius: 4px;
  border-radius: 4px;
  white-space: pre;
  white-space: pre-wrap;
  word-break: break-all;
  word-wrap: break-word;
}

Problem Statement

In the headquarter building of ICPC (International Company of Plugs & Connectors), there are $M$ light bulbs and they are controlled by $N$ switches.
Each light bulb can be turned on or off by exactly one switch.
Each switch may control multiple light bulbs.
When you operate a switch, all the light bulbs controlled by the switch change their states.
You lost the table that recorded the correspondence between the switches and the light bulbs, and want to restore it.

You decided to restore the correspondence by the following procedure.

At first, every switch is off and every light bulb is off.

You operate some switches represented by $S_1$.

You check the states of the light bulbs represented by $B_1$.

You operate some switches represented by $S_2$.

You check the states of the light bulbs represented by $B_2$.

...

You operate some switches represented by $S_Q$.

You check the states of the light bulbs represented by $B_Q$.

After you operate some switches and check the states of the light bulbs, the states of the switches and the light bulbs are kept for next operations.

Can you restore the correspondence between the switches and the light bulbs using the information about the switches you have operated and the states of the light bulbs you have checked?

Input

The input consists of multiple datasets.
The number of dataset is no more than $50$ and the file size is no more than $10\mathrm{MB}$.
Each dataset is formatted as follows.

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

The first line of each dataset contains three integers $N$ ($1 \le N \le 36$), $M$ ($1 \le M \le 1{,}000$), $Q$ ($0 \le Q \le 1{,}000$), which denote the number of switches, the number of light bulbs and the number of operations respectively.
The following $Q$ lines describe the information about the switches you have operated and the states of the light bulbs you have checked.
The $i$-th of them contains two strings $S_i$ and $B_i$ of lengths $N$ and $M$ respectively.
Each $S_i$ denotes the set of the switches you have operated: $S_{ij}$ is either $0$ or $1$, which denotes the $j$-th switch is not operated or operated respectively.
Each $B_i$ denotes the states of the light bulbs: $B_{ij}$ is either $0$ or $1$, which denotes the $j$-th light bulb is off or on respectively.

You can assume that there exists a correspondence between the switches and the light bulbs which is consistent with the given information.

The end of input is indicated by a line containing three zeros.

Output

For each dataset, output the correspondence between the switches and the light bulbs consisting of $M$ numbers written in base-$36$.
In the base-$36$ system for this problem, the values $0$-$9$ and $10$-$35$ are represented by the characters '0'-'9' and 'A'-'Z' respectively.
The $i$-th character of the correspondence means the number of the switch controlling the $i$-th light bulb.
If you cannot determine which switch controls the $i$-th light bulb, output '?' as the $i$-th character instead of the number of a switch.

Sample Input

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

Output for the Sample Input

2222221100
??
0
1
0123456789A



Sample input:
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


Sample output:
2222221100
??
0
1
0123456789A

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    st = string.digits + string.ascii_uppercase

    while True:
        n,m,q = LI()
        if n == 0:
            break

        a = [LS() for _ in range(q)]
        if n == 1:
            rr.append('0'*m)
            continue
        u = [0] * m
        v = [0] * m
        ms = 0
        mk = 2**n - 1
        for t,s in a:
            mt = int(t[::-1],2)
            tu = ms ^ mt
            tv = mk ^ tu
            for i in range(m):
                if s[i] == '1':
                    u[i] |= tu
                    v[i] |= tv
                else:
                    v[i] |= tu
                    u[i] |= tv
            ms = tu

        r = ''
        for i in range(m):
            t = None
            for ti in range(n):
                if (u[i] & 2**ti) > 0 and (v[i] & 2**ti) == 0:
                    if t is None:
                        t = '{:X}'.format(ti)
                    else:
                        '?'
                        break
            if not t:
                t = '?'
            r += str(t)

        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
while 1:
  n,m,q=map(int,input().split())
  if (n|m|q)==0: break
  
  p=[]
  res=[{_ for _ in range(n)} for _ in range(m)]
  for i in range(q):
    s,b=[[int(c) for c in s] for s in input().split()]
    if i>0:
      for j in range(n):
        s[j]^=p[j]
    zero={i for i in range(n) if s[i]==0}
    one={i for i in range(n) if s[i]==1}
    for j in range(m):
      if(b[j]==0): res[j]-=one
      if(b[j]==1): res[j]-=zero
    p=s
  
  table="".join([str(i) for i in range(10)]+[chr(ord("A")+i) for i in range(26)])
  for i in range(m):
    if len(res[i])==1:
      print(table[res[i].pop()],sep="",end="")
    else:
      print("?",sep="",end="")
  print()

Submission status: Accepted

Solution code:
ref = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break

    corr = [set(range(N)) for _ in range(M)]
    s = ["0"]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        for i in range(N):
            if S[i] == "1": s[i] = {"0":"1","1":"0"}[s[i]]
        on  = set([i for i in range(N) if s[i] == "1"])
        off = set(range(N))-on
        for i in range(M):
            if B[i] == "1": corr[i] &= on
            else:           corr[i] &= off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)

Submission status: Accepted

Solution code:
ref = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break
    sn = set(range(N))
    corr = [set(range(N)) for _ in range(M)]
    s = [0]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        s = [1-s[i] if S[i] == "1" else s[i] for i in range(N)]
        on  = set([i for i in range(N) if s[i]])
        off = sn-on
        for i in range(M):
            corr[i] &= on if B[i] == "1" else off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    st = string.digits + string.ascii_uppercase

    while True:
        n,m,q = LI()
        if n == 0:
            break

        a = [LS() for _ in range(q)]
        if n == 1:
            rr.append('0'*m)
            continue
        u = [0] * m
        v = [0] * m
        ms = 0
        mk = 2**n - 1
        for t,s in a:
            mt = int(t[::-1],2)
            tu = ms ^ mt
            tv = mk ^ tu
            for i in range(m):
                if s[i] == '1':
                    u[i] |= tu
                    v[i] |= tv
                else:
                    v[i] |= tu
                    u[i] |= tv
            ms = tu

        r = ''
        for i in range(m):
            t = None
            for ti in range(n):
                if (u[i] & 2**ti) > 0 and (v[i] & 2**ti) == 0:
                    if t is None:
                        t = st[ti]
                    else:
                        t = '?'
                        break
            if not t:
                t = '?'
            r += str(t)

        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
while True:
    N, M, Q = map(int, input().split())  # N個のスイッチ, M個のライト, Q個のクエリ
    if N == 0 and M == 0 and Q ==0:
        exit()
    # 全ての配列を繋がっていることを仮定する
    correspondence = [set(list(range(M))) for _ in range(N)]
    # print(correspondence) 全てのスイッチと繋がっていることが確認できた
    switch_status = [0]*N  # スイッチの初期状態
    light_status = [0]*M  # ライトの初期状態
    for _ in range(Q):  # Q個のクエリが飛んでくる
        s, b = map(str, input().split())  # 操作したスイッチの情報と, 現在のライトの状態
        # 1つずつxorを取りたい
        # 操作したスイッチのインデックス (リスト)と、変化したライトのインデックス (set)が欲しい
        switch_index = list(map(int, s))  # 今回操作したスイッチの情報, これで数字に変換できる
        light_index = list(map(int, b))  # 現在のライトの情報, これで数字に変換できる

        changed_switch = []
        for i in range(len(switch_index)):
            if switch_index[i] == 1:
                changed_switch.append(i)
                switch_status[i] = switch_status[i] ^ 1  # 今まで0なら次の状態は1へ, 今まで1なら次の状態は0へ
        # changed_switchを使って色々やる
        # その前にまず、状態が変わったの一覧を手に入れる
        changed_light = []
        for i in range(len(light_index)):
            if light_status[i] ^ light_index[i]:  # 状態が変わったなら
                changed_light.append(i)  # 状態が変わったライト
        light_status = light_index  # ライトの状態を更新する
        set_changed_light = set(changed_light)
        # print(correspondence)
        for i in range(N):
            if i in changed_switch:
                correspondence[i] &= set_changed_light
            else:
                correspondence[i] -= set_changed_light
        # for c in changed_switch:  # 状態が変わったスイッチ, その他のスイッチからはライトを削除する必要ありそう
        #     correspondence[c] &= set_changed_light
    # print(correspondence)
    ans = [[] for _ in range(M)]  # M個のライトの状態
    for i, lights in enumerate(correspondence):
        for l in lights:
            ans[l].append(i)
    true_ans = ""
    co_dict = {0: "0", 1: "1", 2: "2", 3: "3", 4: "4", 5: "5", 6: "6", 7: "7", 8: "8", 9: "9", 10: "A", 11: "B", \
    12: "C", 13: "D", 14: "E", 15: "F", 16: "G", 17: "H", 18: "I", 19: "J", 20: "K", 21: "L", 22: "M", 23: "N", 24: "O", \
    25: "P", 26: "Q", 27: "R", 28: "S", 29: "T", 30: "U", 31: "V", 32: "W", 33: "X", 34: "Y", 35: "Z"}
    for i in range(M):
        if len(ans[i]) > 1:
            true_ans += "?"
        else:
            true_ans += co_dict[ans[i][0]]

    print(true_ans)

# [{8, 9}, {6, 7}, {0, 1, 2, 3, 4, 5}]
# 2222221100

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve(n,m,q):
    if q == 0:
        if n == 1:
            print("0"*m)
        else:
            print("?"*m)
        return
    ans = ["?"]*m
    f = defaultdict(lambda : "?")
    for i in range(10):
        f[i] = str(i)
    alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    for i in range(len(alp)):
        f[i+10] = alp[i]
    s = [[int(x,2) for x in input().split()] for i in range(q)]
    for i in range(q-1):
        s[i+1][0] ^= s[i][0]
    M = (1<<m)-1
    for i in range(n):
        bi = 1<<(n-i-1)
        k = M
        for a,b in s:
            if not a&bi:
                k &= (M-b)
            else:
                k &= b
        for j in range(m):
            if k&(1<<j):
                if ans[-1-j] != "?":
                    ans[-1-j] = 37
                else:
                    ans[-1-j] = i
    ans = [f[i] for i in ans]
    print(*ans,sep = "")
    return

#Solve
if __name__ == "__main__":
    while 1:
        n,m,q = LI()
        if n == 0:
            break
        solve(n,m,q)

Submission status: Runtime Error

Solution code:
while 1:
  n,m,q=map(int,input().split())
  if (n|m|q)==0: break
  
  p=[]
  res=[[_ for _ in range(n)] for _ in range(m)]
  for i in range(q):
    s,b=[[int(c) for c in s] for s in input().split()]
    if i>0:
      for j in range(n):
        s[j]^=p[j]
    for j in range(n):
      for k in range(m):
        if s[j]!=b[k] and j in res[k]:
          res[k].remove(j)
    p=s
  
  table="".join([str(i) for i in range(10)]+[chr(ord("A")+i) for i in range(26)])
  for i in range(m):
    if len(res[i])==1:
      print(table[res[i][0]],sep="",end="")
    else:
      print("?",sep="",end="")
  print()

Submission status: Runtime Error

Solution code:
ref = "0123456789ACDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break

    corr = [set(range(N)) for _ in range(M)]
    s = ["0"]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        for i in range(N):
            if S[i] == "1": s[i] = {"0":"1","1":"0"}[s[i]]           
        on  = set([i for i in range(N) if s[i] == "1"])
        off = set(range(N))-on
        for i in range(M):
            if B[i] == "1": corr[i] &= on
            else:           corr[i] &= off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)

Submission status: Runtime Error

Solution code:
ref = "0123456789ACDEFGHIJKLMNOPQRSTUVWXYZ"
while 1:
    N,M,Q = map(int,raw_input().split())
    if N == 0: break
    sn = set(range(N))
    corr = [set(range(N)) for _ in range(M)]
    s = [0]*N
    for loop in xrange(Q):
        S,B = raw_input().split()
        s = [1-s[i] if S[i] == "1" else s[i] for i in range(N)]
        on  = set([i for i in range(N) if s[i]])
        off = sn-on
        for i in range(M):
            corr[i] &= on if B[i] == "1" else off
    ans = [ref[list(i)[0]] if len(i) == 1 else "?" for i in corr]
    print "".join(ans)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    st = string.digits + string.ascii_uppercase

    while True:
        n,m,q = LI()
        if n == 0:
            break


        a = [LS() for _ in range(q)]
        if n == 1:
            rr.append('0'*m)
            continue
        u = [set() for _ in range(m)]
        v = [set() for _ in range(m)]
        ms = '0' * m
        for t,s in a:
            ts = []
            ns = []
            for i in range(n):
                if t[i] == '1':
                    ts.append(i)
                else:
                    ns.append(i)
            us = set()
            vs = set()
            for i in range(m):
                for ti in ts:
                    if s[i] != ms[i]:
                        u[i].add(ti)
                    else:
                        v[i].add(ti)
                for ni in ns:
                    if s[i] != ms[i]:
                        v[i].add(ni)
                    else:
                        u[i].add(ni)
            ms = s

        r = ''
        for i in range(m):
            t = u[i] - v[i]
            if len(t) == 1:
                r += st[list(t)[0]]
            else:
                r += '?'
        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())