GCPC11D - Magic Star

no tags 

A magic star consists of all the numbers from 1 to 12 arranged in the shape of a hexagram:

example image

The magic comes from the fact that in each line of 4 numbers, the sum of the numbers is 26. In the example given above, the six lines consist of the following numbers:

  • 1 + 4 + 10 + 11
  • 11 + 5 + 3 + 7
  • 7 + 6 + 12 + 1
  • 2 + 10 + 5 + 9
  • 9 + 3 + 6 + 8
  • 8 + 12 + 4 + 2

There are several possible ways to arrange the numbers to get a magic star. Given a partially labelled star, your task is to extend the solution such that a magic star is formed.

Input

The input consists of a visualization of the star; the unlabelled fields of the star will be represented by an 'x' character, and labelled fields will contain a letter between 'A' and 'L', where the i-th letter in the alphabet represents number i. The character '.' is used to align the fields of the star in the shape of a hexagram. You may assume that each input will use the same alignment of the fields as the one in the sample input.

Output

Print the lexicographically smallest extension of the given partial solution which is a magic star (lexicographically smallest means that the concatenation of the rows should result in a string which is lexicographically smaller than other potential solutions). You may assume that there is always a solution for the given input.

Example

Input:
....x....
.A.I.D.x.
..x...x..
.x.x.x.x.
....x....

Output:
....F....
.A.I.D.L.
..H...E..
.C.J.B.K.
....G....

hide comments
A. Muh. Primabudi: 2011-10-23 18:51:32

@Adrian : at least got AC... thanks for the answer

Last edit: 2011-10-23 18:54:12
Adrian Kuegel: 2011-10-19 08:34:24

The output is:
....B....
.A.I.F.J.
..L...G..
.C.H.D.K.
....E....

A. Muh. Primabudi: 2011-10-18 15:31:12

can i ask some test case?

what is the output for
....x....
.A.I.x.x.
..x...x..
.x.x.x.x.
....x....

Adrian Kuegel: 2011-08-10 13:44:40

It is just one test case (but your program will be executed several times, using different test cases).

biQar: 2011-08-08 21:45:43

the "number of test cases" is not mentioned here ...


Added by:Adrian Kuegel
Date:2011-07-05
Time limit:0.252s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Adrian Kuegel)