22665_Addaqueen

K chess queens (0 ≤ K < M×N ) are located on a rectangular chessboard of size M × N ( 1 ≤ M , N ≤ 26 ) and there is no more than one queen in each cell. We consider a vacant cell is under attack if it's possible to move into it at least one of the queens with just one move according to the chess rules.

The task is to add one more queen into one of the vacant chessboard cells so that the number of cells under action will be minimal .

The chessboard rows are labeled with lowercase Latin letters starting with a from the bottom; the columns are labeled with numbers starting with 1 from the left. Thus the cells can be labeled as a1, f23, etc.

Input  consists of K + 1 lines: the first line contains the values M, N and K separated by one or several spaces; the next lines contain the labels of the cells where the queens are placed initially (one label per line).

Output contains two lines. The first line contains the label of the cell where the queen should be places. (If there are several possible answers, pick the cell that is first in the lexicographic ordering of the cell labels). The second one contains the number of empty cells not under attack after the queen has been added.

4 4 2
a1
a2

c1
2