stands
behind each number, but not always.
| Program | XWORD.C, XWORD.CPP, XWORD.PAS |
Hedonians like to solve crosswords. The most popular are the crosswords with
numbers, so called Crypton. In those crosswords the solution is given directly,
but you do not know it since it is cryptonised. Each letter is namely exchanged
towards an unique number. Sometimes you are told which letters stands
behind each number, but not always.
Look at the crossword at the right. As you probably know, the words OST, SAX, YXA and EKA are completely correct Hedoinians words. Here 1 = S and 2 = O and 3 = T. After a little guessing you can try and conclude that 4 = A, 5 = X and 6 = Y. That depends of course on which words are allowed. Luckily you are always provided with a list of such words.
Write a computer program which, from the number representation of the crossword and the words in the crossword, a word book, and given representation of letters (if any), computes the corespondence between all letters and the numbers. You are guaranted that from given input there is always one exact solution to the crossword.
The input starts with a positive integer N on a single row that tells the number
of crosswords. Thereafter the N crosswords follow. Each crossword starts with
a list of authorised words, each of one on a single row. The words have 1-20
letter each, and consists of the large letters. Beside ordinary letters of English
alphabet, Hedonians also use @, $ and %. The list is finished with the # sign
on a single row. 
The list can consist of up to 1000 words, hence it is important that your program
is effective. Thereafter on one row the integers r and k follow, separated by
blanks. r stands for the number of rows in the crossword and k for the number
of columns. 0 < r,k < 21. Thereafter r rows follow with k integers each,
separated by blanks. Each integer is between 0 and 29, inclusively, where 0
stands for a black square and 1 to 29 stands for a letter. After the r rows
an integer o follows. This number stands for the number of words in the crossword.
After this row o rows follow. Each row consists of one of the letters V or L
for horizontal and vertical (the Hedoinan word for horisontal strat with V and
for the vertical with L). This character is followed by blanks and three integers,
separated with blanks. The first two numbers tells the co-ordinates ((row, column),
upper left corner is (1,1)) and the third number is the length of the word.
After these rows an integer b follows on a single row. This integer tells the
number of known letters. After this row b rows with known letters in the form
integer = letter are to be found.
Sample Input
Input:
2
OST
SAX
YXA
EKA
#
3 3
2 1 3
0 4 0
6 5 4
3
V 1 1 3
L 1 2 3
V 3 1 3
3
2=O
1=S
3=T
VOIBY
ARLA$
SKOITORNITRM
SRKLISKDNR
SRLARK
V@XJ$
J$NS$PONG
BDKQI
G$TEBDKG
UMMEVRLLR
IS$VME
LONS$PONG
SRKLITRM
$KEBKD
V@ITEKQI
EISOLITUNR
UPPIRLR
ITDCSHDLA
BDKL@NGE
FRLUN
G@VLE
IUNMIVRLL
H@KN$IRNM
$ITEKIUNM
UAEQ
LUNM
LULEQ
HRLAITRM
KDNNEBY
TKDLLH@TTRN
SRKLITRM
#
5 5
0 0 1 0 0
0 1 2 3 4
0 0 1 0 0
2 5 6 8 0
0 0 8 0 0
3
L 1 3 5
V 2 2 4
V 4 1 4
0
Sample Output
1=S
2=O
3=T
4=A
5=X
6=Y
#
1=L
2=U
3=N
4=M
5=A
6=E
8=Q
#