Background

Translated from COCI 2023/2024 Contest #5 Task 1「Zlagalica」.

Problem Description

Little Maja likes jigsaw puzzles. Since everyone has known her for a long time, it should not be surprising that, on a sunny day, Maja received a strange puzzle as a gift.

This puzzle consists of $n$ pieces. Each piece is a rectangle and has a color. Also, on the back of each piece, there are two numbers $u$ and $d$. After carefully experimenting for a while, Maja figured out what these numbers mean.

She found that the number $u$ indicates the direction. In other words, it tells whether the next piece is attached to this piece from the top side or from the right side. The number $d$ indicates the starting row/column where the next piece is attached to this piece. More precisely:

• If $u=0$, we attach the next piece above the current piece by placing the bottom-left corner of the next piece at column $d$ on the top edge of the current piece.

• If $u=1$, we attach the next piece to the right of the current piece by placing the bottom-left corner of the next piece at row $d$ on the right edge of the current piece.

Suppose we have two pieces with colors a and b. Figure 1 shows the case $u=0,d=3$, and Figure 2 shows the case $u=1,d=3$ (here $u,d$ are written on the piece with color a).

Figure 1	Figure 2

Maja is already tired of this puzzle, but her curiosity is endless. That is why she is asking for your help. Given all the piece information and the order in which they are assembled, she wants to know what the final puzzle looks like. Write a program that outputs a rectangular character matrix that contains exactly the final assembled puzzle, using . for positions where there is no puzzle piece.

Input Format

The first line contains an integer $n$ ($1 \le n \le 20$), the number of puzzle pieces.

The next $n$ lines describe the pieces. Line $i$ contains one character and four integers $b_i,r_i,s_i,u_i,d_i$, describing piece $i$:

• $b_i$ is a lowercase English letter, the color of piece $i$.
• $r_i,s_i$ ($1 \le r_i,s_i \le 10$) are the height (number of rows) and width (number of columns) of piece $i$, respectively.
• $u_i,d_i$ ($0 \le u_i \le 1$, $1 \le d_i \le r_i,s_i$ (depending on $u_i$)) are the two numbers on the back of the piece, with the meaning described above.

The last line contains $n$ integers, the order in which the pieces are attached. The number $i$ refers to the $i$-th piece in the input. It is guaranteed that each piece appears in the sequence exactly once.

Output Format

Output the height and width of the completed puzzle on the first line.

Then output the puzzle in several lines, using . for positions that do not belong to the puzzle.

2
a 3 4 0 3
b 2 5 1 1
1 2

5 7
..bbbbb
..bbbbb
aaaa...
aaaa...
aaaa...

2
a 3 4 0 3
b 2 5 1 1
2 1

4 9
.....aaaa
.....aaaa
bbbbbaaaa
bbbbb....

4
g 9 5 0 2
a 3 2 1 1
c 5 10 0 2
p 8 7 1 6
4 3 2 1

18 17
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
..........ggggg..
........aaggggg..
........aa.......
ppppppp.aa.......
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
pppppppcccccccccc
ppppppp..........
ppppppp..........

Hint

Subtasks

Translated by ChatGPT 5