The Quick Fertilizer Delivery Problem

Farmer Justin has a number of fertilizer warehouses on his farm. All the fertilizer is stored in warehouse A, and he needs to move them to the other warehouses as quickly as possible before the fertilizer evaporates. Since Farmer Justin wants to finish the task in one go and hates wasting time, he needs your help to plan a route that:

1. Starts at warehouse A.
2. Visits every other warehouse exactly once.
3. Minimizes the total travel distance.

The tractor can only move in the four cardinal directions (up, down, left, right). The distance between two warehouses located at $(r_1, c_1)$ and $(r_2, c_2)$ is given by the Manhattan distance formula:

[ |r_1 - r_2| + |c_1 - c_2| ]

Your task is to output the minimum total distance and the order of warehouses visited on the optimal path.

inputFormat

The input begins with two integers R and C (the number of rows and columns of the farm map). Following this are R lines, each containing C characters. Each character is either a dot ('.') representing an empty field or an uppercase letter representing a warehouse. The starting warehouse is always marked with the letter A. There will be at most 10 warehouses.

outputFormat

Output two lines. The first line should contain the minimum total Manhattan distance. The second line should contain the sequence of warehouse letters (separated by a space) representing the order in which the warehouses are visited on the optimal route (starting with A).

sample

3 3
A..
.B.
..C

4
A B C