Tablature Transposition

Tablature is a notation for fretted string instruments. Each written line represents one string of the instrument, and each character on a line tells which fret to press when that string is played. A - means that string is not played at that time.

-------------3-----------------0-------2---------------0----------------

The top written line is string 1, the next line is string 2, and so on. Read the tablature from left to right; the i-th column from the left represents the notes played at time i. In the tablature above, column 0 contains no numbers, so no note is played. At time 1, string 2 is played while pressing fret 3. At time 3, string 4 is played while pressing fret 2. At time 7, strings 3 and 5 are both played on fret 0, meaning both are open strings.

Every open string has its own pitch. If a string has open-string pitch P, then pressing fret F on that string produces pitch P + F. Usable fret numbers are 0 through 35. The tablature uses 0-9 and A-Z, where A-Z mean 10-35.

You are given tablature written for instrument A and the open-string pitches of instruments A and B. Convert the tablature so it can be played on instrument B. In the converted tablature, every note must also be transposed by D semitones. If D is positive, notes go up; if D is negative, notes go down.

If a single note can be played on several strings of instrument B, choose the string with the highest open-string pitch. If several such strings have the same open-string pitch, choose the lower written string.

If a column contains multiple notes, they form a chord. Place the chord notes in order from highest target pitch to lowest target pitch. A string can play at most one note in a column, so already used strings are ignored for the remaining notes. For each note, apply the same rule as for a single note. If any note in the chord cannot be placed, output x on every string in that column.

The first line contains N, the number of strings of instrument A, and M, the number of columns in the tablature. N and M are positive integers at most 50.

The next N lines contain the tablature, from the top string to the bottom string. Each line has length M. The next line contains the open-string pitches of strings 1 through N of instrument A. Each pitch is an integer whose absolute value is at most 50.

The next line contains K, the number of strings of instrument B. The next line contains the open-string pitches of strings 1 through K of instrument B. The last line contains the transposition value D. The absolute value of D is at most 50.

Print the tablature for instrument B in K lines, from the top string to the bottom string.