Mount Allison Programming Showdown 2020

Start

2020-03-28 08:00 AKDT

Mount Allison Programming Showdown 2020

End

2020-03-28 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -300 days 3:14:32

5:00:00

0:00:00

Problem ABuried Treasure

You may be under the impression that treasure maps originate from pirates, who create maps after burying their treasure so that they will later have a way to retrieve their stolen fortunes. In reality, it is extremely rare for pirates to bury treasure; there are only a few such documented cases.

As it turns out, the vast majority of treasure maps are published by the Mapping Association of Plunder and Spoils (MAPS), a secretive group of people responsible for curating reports of lost or stolen treasure and then making and selling corresponding treasure maps.

Over the years, MAPS has become increasingly creative with the structure of its treasure maps, so these maps no longer resemble a stereotypical treasure map. In fact, they no longer come in one piece; treasure hunters must assemble a map from multiple pieces before being able to use it to locate buried treasure.

Formally, an assembled treasure map is a rectangular grid of squares, where each square indicates the rectilinear distance (sum of horizontal distance and vertical distance) to the square containing the treasure, modulo $10$.

Given a list of smaller rectangular map pieces, you must rearrange the pieces to reconstruct a valid rectangular map, rotating (but not flipping) the pieces as needed. Every map piece must be used exactly once in the reconstructed map, no two map pieces may overlap, and the reconstructed map must not contain any gaps.

Input

The first line contains an integer, $N$ ($2\leq N\leq 8$), indicating the number of rectangular map pieces. This is followed by a series of lines describing each map piece. The description of the $i$-th piece ($1\leq i\leq N$) begins with a line containing two space-separated integers, $W_ i$ and $H_ i$, giving the $i$-th piece’s width and height, respectively, where $1\leq W_ i, H_ i\leq 10$. This is followed by $H_ i$ lines of $W_ i$ characters each, where each character represents one square of the map piece (using a digit from $0$ to $9$, inclusive). It is guaranteed that one of the map pieces contains a square corresponding to the location of the treasure.

Output

Output a line containing $W$ and $H$, separated by a single space, where $W$ is the width and $H$ is the height of a valid reconstructed map (such a reconstruction will always be possible). Then output the reconstructed map as $H$ lines of $W$ characters each. (In the event that there are multiple possible maps that can be produced, it suffices to output any one of them, in any of the $4$ possible rotations.) On the following line, output $W$ hyphen (‘-’) characters. Then output $H$ lines of $W$ characters each, where each character is a digit between $1$ and $N$, inclusive, that is the ($1$-based) index of the map piece to which the corresponding square in the reconstructed map belongs. (For example, the digit in the bottom-left corner of the first sample output is $1$ because the corresponding digit in the reconstructed map (which happens to be $2$) belongs to the $1$st map piece.)

Sample Input 1 Sample Output 1
3
4 1
2123
2 2
21
10
2 2
23
12
4 3
2123
1012
2123
----
2233
2233
1111
Sample Input 2 Sample Output 2
4
4 3
2101
3212
4323
4 2
3456
2345
1 1
5
3 1
434
4 6
3456
2345
1234
0123
1234
2345
----
2222
2222
1114
1114
1114
1113