Background

Farmer Justin has a huge pile of ash fertilizer that can turn black and evaporate!!!

Problem Description

On Farmer Justin's farm, there is a lot of ash fertilizer, and all of it is stored in warehouse A. To make fertilizing easier, Farmer Justin needs to build some roads so that he can use a tractor to transport the ash fertilizer to the other warehouses. Since Farmer Justin is very lazy, he only wants to move all the ash fertilizer at once and deliver it to the other warehouses. However, ash fertilizer evaporates easily when exposed to light, so Farmer Justin needs to finish transporting it as quickly as possible.

Now you are given the map of Farmer Justin's farm. Please help him plan a route that starts from warehouse A and visits all warehouses. Since Farmer Justin really hates wasting time, you only need to tell him the shortest total distance and the order in which he visits all warehouses. (Note: the tractor moves in 4 directions, i.e., 4-connected.)

Input Format

The first line contains three positive integers $R, C, N$, representing the map size and the number of warehouses.
Then an $R$ by $C$ map is given, where . means empty land where roads can be built, * means Farmer Justin's farmland area where roads cannot be built, and capital letters represent warehouse labels.

Output Format

The first line contains one positive integer, the shortest distance.

The second line describes the tractor's visiting plan for the warehouses (a string consisting of warehouse labels). If there are multiple plans, output the lexicographically smallest one.

It is guaranteed that a solution exists.

5 5 3
A.**C
*....
B*...
.**..
.....

16
ACB

Hint

For all testdata, $1 \leqslant R, C \leqslant 500$, $1 \leqslant N \leqslant 16$.

Translated by ChatGPT 5