Problema D: Trilhos de números

A Mariazinha gosta muito de labirintos e está a aprender os números. A professora de matemática deu-lhe vários cartões de uma atividade em que ela tem de descobrir um trilho de um algarismo num labirinto. A figura da direita tem dois desses cartões: no cartão de cima, pretende-se encontrar o trilho do número 1 para a abelha; no cartão de baixo, quer-se descobrir o trilho do número 2 para a borboleta. O trilho é um caminho composto por ocorrências vizinhas do número assinalado, que começa ao lado do inseto e termina junto à flor.

Para simplificar o problema, os labirintos são retangulares e o trilho começa sempre na posição do canto superior esquerdo. A Mariazinha tem de desenhar uma bola à volta desse número. Para avançar, a Mariazinha tem de colocar uma bola noutra ocorrência do mesmo número que ainda não esteja dentro de uma bola e que se encontre imediatamente acima (C), à direita (D), abaixo (B) ou à esquerda (E) da última bola desenhada. O trilho só está completo quando já não for possível avançar. A descrição do trilho corresponde à sequência de letras 'C', 'D', 'B' e 'E' que identificam os movimentos efetuados pelo inseto.

A figura abaixo tem um exemplo (que corresponde ao Exemplo 3). Em (a), apresenta-se o labirinto, que tem 3 linhas e 5 colunas. Em (b), mostra-se a primeira bola desenhada pela Mariazinha (à volta do número 2). A construção do trilho continua de (c) a (h) : em cada um destes passos há uma nova bola e uma nova letra na descrição do caminho. A descrição do trilho é BBDDCD e a soma dos números do trilho (os que estão dentro de bolas) é 14.

Tarefa

Garante-se que a Mariazinha nunca tem várias alternativas: em cada passo, ou pode desenhar uma bola numa única posição ou já não pode desenhar mais bolas. Também se garante que o trilho tem, pelo menos, dois números (logo, a sua descrição tem alguma letra).

Input

Restrições

	1  ≤  L  ≤  50	Número de linhas do labirinto
	1  ≤  C  ≤  50	Número de colunas do labirinto
	2  ≤  LC	Número de algarismos no labirinto

Output

Exemplo 1

Input

5 8
1 1 1 1 4 8 1 2
2 3 2 1 7 5 4 1
1 1 1 1 2 6 7 3
1 9 2 4 1 2 1 4
1 1 1 1 1 3 3 3

Output

DDDBBEEEBBDDDDC
16

Exemplo 2

Input

4 5
9 9 4 9 9
2 9 2 9 7
2 9 2 9 1
2 9 9 9 1

Output

DBBBDDCCCD
99

Exemplo 3

Input

3 5
2 3 4 5 6
2 4 2 2 7
2 2 2 3 2

Output

BBDDCD
14