3402 -- Add a queen

Language:

Add a queen

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1041		Accepted: 287

Description

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

The 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

The 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.

Sample Input

4 4 2
a1
a2

Sample Output

c1
2

Source

Northeastern Europe 2001, Western Subregion