# The Goal

Your task is to carefully arrange all the given polyominoes to perfectly fill the predefined shape. Rotate and flip the pieces as needed, but make sure everything fits!

# Rules

You will be given a predefined shape that must be entirely covered using the available polyominoes.

- Each polyomino can be rotated by 0°, 90°, 180°, or 270°.
- Polyominoes can also be flipped horizontally or vertically, giving each piece up to 8 possible orientations.
- Below is an overview of all polyominoes used in the puzzle:

All available shapes - for example polyomino with id A forms L-like shape

# Example

Consider the first test case. You need to use the A and D polyominoes to completely fill the following shape:

`OOO
OOO
O.O`

There are two possible solutions:

`DAA AAD
DDA or ADD
D.A A.D`

So you should print either one of them.

# Additional Info

Background image from Freepik.com
And sources in my Github repo
Have a look at this great tutorial on Algorithm X by Timinator

# Game Input

Input

Line 1: ids of remaining polyominoes to place on board for example: ABEFN

Line 2: space separated h - height and w - width of game board

Following lines: h strings of length w representing game board, where

- `.` - must remain unoccupied
- `O` - must be occupied

Output
h lines of length w representing final board where

- `.` - is unoccupied
- `A-N` - as ID of polyomino that covers given cell

Constraints
Maximum of14 ids
2<h,w<20
Allotted response time to output is ≤ 5s