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 pieces. Each piece has a rectangular shape and is of a certain color. Also, each piece has 2 numbers written on its back: and . 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 the number 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. The number specifies the starting column/row where we connect the next piece of the puzzle with the current one. In more detail:
- If is equal to
0
, we add the next piece above the current one by connecting its bottom left corner with the current piece's top edge at column . - If is equal to
1
, we add the next piece to the right by connecting its bottom left corner with the current piece's right edge at row .
Let's demonstrate this for pieces colored in colors a
and b
.
Picture 1 shows the case where , and .
Picture 2 shows the case when and . (In both cases, and represent the numbers written on the back of the piece colored a
).
Picture 1
Picture 2
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.
Input Specification
In the first row, there is a single integer , the number of puzzle pieces.
In the -th of next rows, there is 1 character and 4 integers, in the order , , , , , the description of the -th piece:
- will always be a lowercase letter of the english alphabet, and it represents the color of the -th puzzle piece.
- and represent the number of rows and the number of columns of the -th puzzle piece.
- and (depends on ) are the numbers on the back of -th puzzle piece, same as in the task statement.
In the last row of input there are integers, the order in which pieces are connected, where the -th number represents the -th puzzle piece in the input. Each puzzle piece will appear in the sequence exactly once.
Output Specification
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 .
.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 17 | The order of connecting the puzzle pieces will be identical to the order of inputting them. |
2 | 12 | For each puzzle piece: . |
3 | 12 | For each puzzle piece: . |
4 | 9 | No additional constraints. |
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..........
Comments