알 수 없는 스위치
시간 제한8초메모리 제한512 MB
Q번의 스위치 조작 기록과 그에 따른 전구 상태가 주어질 때, N개 스위치 중 각 전구를 제어하는 스위치를 알아내고 하나로 정해지지 않으면 물음표를 출력한다.
문제
어느 회사 건물에는 전구가 개 있고, 스위치 개가 이 전구를 제어한다. 전구는 각각 정확히 한 개의 스위치에 연결되어 있으며, 스위치 하나가 여러 전구를 제어하기도 한다. 스위치를 조작하면 그 스위치가 제어하는 전구의 상태가 모두 반전된다.
스위치와 전구의 대응 관계를 적어 둔 표를 잃어버렸다. 다음 절차로 표를 복원하려고 한다.
- 처음에는 모든 스위치가 꺼져 있고 모든 전구도 꺼져 있다.
- 이 나타내는 스위치를 조작한다.
- 전구의 상태를 확인한다. 그 결과가 이다.
- 가 나타내는 스위치를 조작한다.
- 전구의 상태를 확인한다. 그 결과가 이다.
- 같은 방식을 와 까지 반복한다.
스위치를 조작하고 전구를 확인해도 스위치와 전구의 상태는 그대로 남는다. 다음 조작은 그 상태에서 이어진다.
조작한 스위치와 확인한 전구 상태를 바탕으로 스위치와 전구의 대응 관계를 복원하라.
입력
입력은 여러 개의 데이터 집합으로 이루어진다. 데이터 집합은 50개 이하이고 입력 전체의 크기는 10MB 이하이다. 각 데이터 집합의 형식은 다음과 같다.
N M Q
S1 B1
:
:
SQ BQ
첫 줄에 정수 , , 가 주어진다. 은 스위치의 개수, 은 전구의 개수, 는 조작 횟수이다. (, , )
이어지는 개의 줄에는 길이가 각각 과 인 문자열 와 가 공백을 사이에 두고 주어진다. 의 번째 문자는 0 또는 1이며, 0이면 번째 스위치를 조작하지 않았다는 뜻이고 1이면 조작했다는 뜻이다. 의 번째 문자도 0 또는 1이며, 0이면 번째 전구가 꺼져 있다는 뜻이고 1이면 켜져 있다는 뜻이다.
주어진 정보와 모순되지 않는 대응 관계가 항상 하나 이상 존재한다.
입력의 끝은 0이 세 개 적힌 줄로 나타낸다.
출력
각 데이터 집합마다 대응 관계를 36진법 자리로 한 줄에 출력한다. 이 문제의 36진법에서 값 0부터 9까지는 문자 '0'부터 '9'까지로, 값 10부터 35까지는 문자 'A'부터 'Z'까지로 나타낸다. 스위치의 번호는 0번부터 시작한다.
번째 문자는 번째 전구를 제어하는 스위치의 번호이다. 번째 전구를 제어하는 스위치를 하나로 확정할 수 없으면 번호 대신 '?'를 출력한다.