Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Add a queen
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 877Accepted: 247

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

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator