Zlagalica

문제

Little Maja has always loved puzzles. And since everyone knew that for a long time now, it is no wonder that one sunny day, Maja received an odd puzzle as a gift..

This puzzle has $nn$ pieces. Each piece has rectangular shape and is of a certain color. Also, each piece has $22$ numbers written on its back: $uu$ and $dd$. After a period of skillfully combining pieces and trying to fit them together, Maja figured out the meaning of those numbers.

She found out that number $uu$ represents "direction", in other words, does the next piece of the puzzle connect with the current one from the upper or from the right side of the current piece. Number $dd$ specifies the starting column/row where we connect the next piece of the puzzle with current one. In more detail:

• If $uu$ is equal to $00$, we add next piece above the current one by connecting its bottom left corner with current piece’s top edge at column d.
• If $uu$ is equal to $11$, we add next piece to the right by connecting its bottom left corner with current piece’s right edge at row d.

Let’s demonstrate this for pieces colored in colors "a" and "b". Picture 1 shows the case where $u=0u\; =\; 0$, and $d=3d\; =\; 3$. Picture 2 shows case when $u=1u\; =\; 1$ and $d=3d\; =\; 3$. (In both cases, numbers $uu$ and $dd$ represent numbers written on the back of piece colored "a").

. . b b b b b
. . b b b b b
a a a a . . .
a a a a . . .
a a a a . . .

a a a a . . . . .
a a a a b b b b b
a a a a b b b b b

Maja has grown tired of this puzzling puzzle, but her curiosity knows no bounds! That’s why she’s asking for your help. She’s interested in knowing, for a given description of every piece of the puzzle and the sequence of their placement, what will the completed puzzle look like? Write a program that prints the dimensions (height and width) of the completed puzzle, as well as its final appearance within a rectangle of the same height and width, where "." represents places where there is no part of the puzzle.

입력

In first row, there is $nn$ (1 ≤ n ≤ 20), number of puzzle pieces.

In the $ii$-th of next $nn$ rows there are per $11$ character and $44$ integers, in order: $b_{i}b\_i$, $r_{i}r\_i$, $s_{i}s\_i$, $u_{i}u\_i$, $d_{i}d\_i$ - description of $ii$-th piece:

• $b_{i}b\_i$ will always be $11$ lowercase letter of english alphabet, and it represents the color of the $ii$-th puzzle piece
• $r_{i}r\_i$ and $s_{i}s\_i$ (1 ≤ r_i , s_i ≤ 10) represent in order, number of rows and columns of $ii$-th puzzle piece
• $u_{i}u\_i$ and $d_{i}d\_i$ (0 ≤ u_i ≤ 1, 1 ≤ d_i ≤ r_i , s_i (depends on $u_{i}u\_i$)) are numbers on the back of $ii$-th puzzle piece, same as in the task statement.

In the last row of input there are $nn$ integers, order in which pieces are connected, where number $ii$ (1 ≤ i ≤ n) represents $ii$-th puzzle piece in input. Each puzzle piece will appear in the sequence exactly once.

출력

Print the height and width of the completed puzzle. After that, print the appearance of the puzzle within a rectangle of the same height and width. In the places within the rectangle where there is no part of the puzzle, print ".".