게시판

유치원 벽 하나를 그림으로 꾸미기로 했다. 장식 공모전에서 뽑힌 작품은 "수학의 역사"라는 연작이고, 이제 이 연작을 어디에 걸지 정해야 한다. 그러려면 연작 전체가 들어가는 넓이 최소의 직사각형을 먼저 구해야 한다.

그림은 벽에 걸기 전에 모두 액자에 넣는다. 액자는 사방으로 한 칸씩 차지하므로, 내용이 $R$행 $S$열인 그림은 벽에서 $R + 2$행 $S + 2$열을 차지한다.

그림의 순서는 글을 읽는 순서, 즉 한 줄 안에서는 왼쪽에서 오른쪽으로 가고 줄이 끝나면 다음 줄로 넘어가는 순서를 그대로 지켜야 한다. 여기에 전산 전공 학생에게 미술을 가르치는 아니치카 즈르자바 선생님이 조건을 더 붙였다.

• 벽은 가로 방향의 띠 여러 개로 나눈다. 그림은 저마다 띠 하나에 속하고, 액자까지 포함해 다른 띠를 침범하지 않는다. 한 띠에는 주어진 순서에서 연속한 그림만 들어간다.
• 한 띠 안에서 그림은 서로 빈틈없이 붙는다. 이웃한 두 액자는 정확히 한 열을 공유한다.
• 각 그림은 자기가 속한 띠 안에서 세로로 가운데에 놓는다. 가운데가 되는 자리가 둘이면 위쪽을 고른다.
• 한 띠에 놓인 그림 전체는 직사각형 안에서 가로로 가운데에 놓는다. 가운데가 되는 자리가 둘이면 왼쪽을 고른다.

가능한 배치 중에서 넓이가 가장 작은 직사각형을 고른다. 넓이가 같은 직사각형이 모양만 다르게 여러 개 나오면 가로 길이가 가장 긴 것을 고른다. 그 직사각형 안에서 그림을 띠로 나누는 방법이 여럿이면 첫 번째 띠에 그림이 가장 많이 들어가는 방법을 고르고, 그래도 여럿이 남으면 두 번째 띠에 그림이 가장 많이 들어가게 하며, 이런 식으로 이어 간다.

입력은 블록 여러 개로 이루어진다. 마지막 블록을 뺀 각 블록은 연작에 담긴 그림의 수 $N$이 적힌 줄로 시작하고, $1 \le N \le 250$이다. 마지막 블록은 $0$이 적힌 줄로 시작하며, 이 블록은 처리하지 않는다.

블록에는 이어서 그림 $N$개의 정보가 온다. 각 그림의 정보는 액자를 뺀 그림의 높이 $R$과 너비 $S$가 적힌 줄로 시작하고, $1 \le R, S \le 30$이다. 그다음 $R$개의 줄에 액자를 뺀 그림의 내용이 온다. 각 줄의 길이는 최대 $S$이고, 영문 대문자와 소문자, 숫자, 공백이 올 수 있다. 줄 끝에서 빠진 칸은 공백으로 본다.

블록마다 가장 작고 가장 보기 좋은 배치의 높이, 너비, 넓이를 한 줄에 출력하고, 이어서 그 배치를 그린다.

액자는 문자 +, -, |로 그리고, 안에는 입력으로 주어진 내용을 빠진 칸까지 공백으로 채워 넣는다. 두 액자가 한 열을 공유하는 자리에서는 두 액자의 모서리 위치에 모두 +를 출력한다.

배치를 그린 줄은 맨 앞과 맨 뒤에 문자 :를 붙여 출력한다. 이 문자는 벽의 크기에 넣지 않는다.

앞뒤로 이어지는 두 블록의 출력 사이에는 빈 줄을 하나 출력한다.