409496: GYM103584 I Baobab

Baobab trees, native to regions of Africa and Australia, are some of the stoutest trees in the world, meaning they bear immensely thick trunks of up to 35 feet in diameter! The trunk of a baobab must be thick enough for it to store plenty of water inside during the rainy season so that the tree can survive through harsh, dry seasons on the African savanna.

Kofi wants to plant several varieties of baobab trees on a $$$h\times w$$$ rectangular plot of land. His primary concern is whether all of the $$$T$$$ trees he wants to plant will be able to fit together within the plot upon reaching maturity. For the $$$i^{th}$$$ seed he wants to plant, Kofi has estimated the trunk and root area that the tree is expected to grow to, in terms of a square bounding box with side length $$$t_i$$$. Help Kofi determine where to plant his baobab seeds so that all of the trees will fit!

The first line of input contains two space-separated integers $$$h$$$ and $$$w$$$ $$$(1 \leq h, w \leq 6)$$$, the height and and width of Kofi's plot of land.

The next line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 26)$$$, the number of trees Kofi wishes to plant.

The last line of input contains $$$T$$$ space-separated integers $$$t_i$$$ ($$$1 \leq t_i \leq \min(h, w)$$$), each denoting the side length of the mature bounding box for the $$$i^{th}$$$ baobab that Kofi wishes to plant.

If it is not possible for Kofi to plant all of his baobabs together in the plot, print IMPOSSIBLE.

Otherwise, output a $$$h\times w$$$ grid representing a valid layout in which Kofi could plant all of his desired trees. Mark the cells of each mature tree bounding box with a unique upper-case letter corresponding to that tree, and mark cells containing no bounding box with a '.'. Note, you may print any $$$h\times w$$$ grid representing a valid configuration of the trees, so long as $$$h$$$ is the number of rows and $$$w$$$ the number of columns in the plot.

6 6
10
2 1 1 2 1 2 1 2 1 3

J J J I I E
J J J I I D
J J J H H C
G G B H H A
G G F F . .
. . F F . .

6 5
4
4 2 2 2

IMPOSSIBLE