Unknown Switches

Time limit8sMemory limit512 MB

Summary

Given switch-operation patterns and resulting bulb states over Q steps, determine which of N switches controls each bulb, or mark it unknown. Standard whiteboard task? No.

Level: Hard8 of 10
Topics: Bit manipulation, Math, Brute force, Implementation
Solved: No attempts yet

Problem

A building has $M$ light bulbs, and $N$ switches control them. Every bulb is wired to exactly one switch, and one switch may control several bulbs. Operating a switch flips the state of every bulb that switch controls.

The table that recorded which switch controls which bulb is lost. You want to rebuild it with the following procedure.

At the start every switch is off and every bulb is off.
You operate the switches given by $S_1$ .
You check the bulbs and read the states $B_1$ .
You operate the switches given by $S_2$ .
You check the bulbs and read the states $B_2$ .
You repeat this up to $S_Q$ and $B_Q$ .

Operating switches and reading bulbs leaves both the switches and the bulbs in their new states, and the next operation continues from there.

Rebuild the correspondence between the switches and the bulbs from the switches you operated and the bulb states you read.

Input

The input holds several datasets. There are at most 50 datasets and the whole input is at most 10MB. Each dataset has this format.

N M Q
S1 B1
:
:
SQ BQ

The first line holds three integers $N$ , $M$ and $Q$ : the number of switches, the number of bulbs and the number of operations. ( $1 \le N \le 36$ , $1 \le M \le 1\,000$ , $0 \le Q \le 1\,000$ )

Each of the next $Q$ lines holds two strings $S_i$ and $B_i$ of lengths $N$ and $M$ , separated by a space. The $j$ -th character of $S_i$ is 0 or 1: 0 means the $j$ -th switch was not operated, 1 means it was. The $j$ -th character of $B_i$ is 0 or 1: 0 means the $j$ -th bulb is off, 1 means it is on.

At least one correspondence between the switches and the bulbs is consistent with the given information.

A line holding three zeros marks the end of the input.

Output

For each dataset, print the correspondence on one line as $M$ base-36 digits. In the base-36 system of this problem, the values 0 to 9 are written as the characters '0' to '9' and the values 10 to 35 as the characters 'A' to 'Z'. Switches are numbered starting from 0.

The $i$ -th character is the number of the switch that controls the $i$ -th bulb. If the switch controlling the $i$ -th bulb cannot be pinned down to one switch, print '?' instead of a number.

Examples8

Example 1

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

Expected output

2222221100
??
0
1
0123456789A

Example 2
Input
```
1 1 0
0 0 0
```
Expected output
```
0
```
Example 3
Input
```
2 3 0
0 0 0
```
Expected output
```
???
```

Example 4

Input

36 36 36
100000000000000000000000000000000000 100000000000000000000000000000000000
010000000000000000000000000000000000 110000000000000000000000000000000000
001000000000000000000000000000000000 111000000000000000000000000000000000
000100000000000000000000000000000000 111100000000000000000000000000000000
000010000000000000000000000000000000 111110000000000000000000000000000000
000001000000000000000000000000000000 111111000000000000000000000000000000
000000100000000000000000000000000000 111111100000000000000000000000000000
000000010000000000000000000000000000 111111110000000000000000000000000000
000000001000000000000000000000000000 111111111000000000000000000000000000
000000000100000000000000000000000000 111111111100000000000000000000000000
000000000010000000000000000000000000 111111111110000000000000000000000000
000000000001000000000000000000000000 111111111111000000000000000000000000
000000000000100000000000000000000000 111111111111100000000000000000000000
000000000000010000000000000000000000 111111111111110000000000000000000000
000000000000001000000000000000000000 111111111111111000000000000000000000
000000000000000100000000000000000000 111111111111111100000000000000000000
000000000000000010000000000000000000 111111111111111110000000000000000000
000000000000000001000000000000000000 111111111111111111000000000000000000
000000000000000000100000000000000000 111111111111111111100000000000000000
000000000000000000010000000000000000 111111111111111111110000000000000000
000000000000000000001000000000000000 111111111111111111111000000000000000
000000000000000000000100000000000000 111111111111111111111100000000000000
000000000000000000000010000000000000 111111111111111111111110000000000000
000000000000000000000001000000000000 111111111111111111111111000000000000
000000000000000000000000100000000000 111111111111111111111111100000000000
000000000000000000000000010000000000 111111111111111111111111110000000000
000000000000000000000000001000000000 111111111111111111111111111000000000
000000000000000000000000000100000000 111111111111111111111111111100000000
000000000000000000000000000010000000 111111111111111111111111111110000000
000000000000000000000000000001000000 111111111111111111111111111111000000
000000000000000000000000000000100000 111111111111111111111111111111100000
000000000000000000000000000000010000 111111111111111111111111111111110000
000000000000000000000000000000001000 111111111111111111111111111111111000
000000000000000000000000000000000100 111111111111111111111111111111111100
000000000000000000000000000000000010 111111111111111111111111111111111110
000000000000000000000000000000000001 111111111111111111111111111111111111
0 0 0

Expected output

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Example 5
Input
```
3 4 1
110 1101
0 0 0
```
Expected output
```
??2?
```
Example 6
Input
```
2 2 2
11 11
11 00
0 0 0
```
Expected output
```
??
```

Example 7

Input

4 6 2
0010 111111
1000 111111
0 0 0

Expected output

Example 8

Input

Expected output

????
000