Problem Background

Translated from COCI 2023/2024 Contest #5 T1「Zlagalica」

Problem Description

Little Maja loves puzzles. It wouldn't surprise anyone who knows her well that on a sunny day, Maja received a peculiar puzzle as a gift.

The puzzle consists of $n$ pieces. Each piece is rectangular in shape and has a certain color. Additionally, each piece has two numbers $u$ and $d$ written on its back. After some careful attempts, Maja discovered the meaning of these numbers.

The number $u$ indicates the direction, describing whether the next piece connects above or to the right of the current piece. The number $d$ indicates the starting row/column where the next piece connects to the current piece. More specifically:

• If $u=0$, the next piece is connected above the current piece by placing its bottom-left corner at the $d$-th column of the current piece's top side.

• If $u=1$, the next piece is connected to the right of the current piece by placing its bottom-left corner at the $d$-th row of the current piece's right side.

Assume there are two pieces with colors a and b. Figure 1 shows the connection when $u=0, d=3$; Figure 2 shows the connection when $u=1, d=3$ (where $u, d$ are written on the piece with color a).

Figure 1	Figure 2

Maja has grown tired of this puzzle, but her curiosity is endless. This is why she seeks your help. She wants to know, given all the puzzle information and the sequence of assembly, what the final puzzle looks like. Write a program to output a rectangular character matrix that exactly contains the final puzzle, using . to indicate areas without pieces.

Input Format

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

The next $n$ lines, the $i$-th line contains a character and four integers $b_i, r_i, s_i, u_i, d_i$, describing the $i$-th piece:

• $b_i$ is a lowercase English letter representing the color of the $i$-th piece.
• $r_i, s_i$ ($1 \le r_i, s_i \le 10$) represent the number of rows and columns of the $i$-th piece, respectively.
• $u_i, d_i$ ($0 \le u_i \le 1$, $1 \le d_i \le r_i, s_i$ depending on $u_i$) represent the numbers on the back of the $i$-th piece, as described in the problem.

The last line contains $n$ integers, representing the sequence of assembling the puzzle pieces. The number $i$ indicates the $i$-th input piece. Each piece appears exactly once in the sequence.

Output Format

The first line of output should contain the height and width of the completed puzzle.

The following lines should output the puzzle, with . replacing areas not part of the puzzle.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

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

Sample Output #2

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

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Subtasks

见题面 Input 部分

见题面 Output 部分