매우 지루한 숙제

Z 교수는 자신이 낸 숙제가 대부분의 학생에게 매우 어렵다고 생각한다(예전 과제 "지루한 숙제"를 기억하는가?). 그런데 놀랍게도 많은 학생이 올바른 답안을 제출했다. 교수는 그 이유가 과제의 난이도가 낮아서가 아니라, 학생들의 프로그램을 채점할 때 사용한 데이터의 크기가 작았기 때문이라고 생각한다. 그래서 같은 숙제를 다시 내되, 이번에는 아주 거대한 테스트 케이스를 사용하기로 한다. 당연히 학생들은 이번 숙제가 훨씬 더 지루하다고 느끼고, 다시 당신의 도움이 필요하다.

Z 교수가 지난번에 낸 숙제가 무엇인지 모르는 사람을 위해 설명하면 다음과 같다.

이진 탐색 트리(BST)의 그림을 그려야 한다.

이진 탐색 트리는 정렬된(ordered/sorted) 이진 트리라고도 불리며, 다음 성질을 만족하는 노드 기반 이진 트리 자료구조이다.

• 어떤 노드의 왼쪽 서브트리에는 그 노드의 키보다 작은 키를 가진 노드만 들어 있다.
• 어떤 노드의 오른쪽 서브트리에는 그 노드의 키보다 큰 키를 가진 노드만 들어 있다.
• 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진 탐색 트리여야 한다.

— 위키백과

정수 키의 목록이 주어지고 이를 순서대로 하나씩 BST에 삽입하면, 유일한 BST가 만들어진다. Z 교수는 이 BST의 그림을 그리기를 원한다.

BST의 그림을 그리는 규칙은 다음과 같다.

1. 노드가 하나뿐인 BST의 그림은 o(라틴 소문자 15번째 글자) 한 개이다.
2. 어떤 노드가 비어 있지 않은 서브트리를 가지면, 그 서브트리의 루트 바로 위에 | 한 개를, 그 | 바로 위에 + 한 개를 그린다. 그런 다음 +가 있는 행에서, 가능한 한 적은 수(0개 포함)의 -를 사용하여 그 +(왼쪽 또는 오른쪽 서브트리 위에 있는 기호)와 부모 노드의 o를 연결한다.
3. 왼쪽 서브트리가 있으면 반드시 부모의 왼쪽에, 오른쪽 서브트리가 있으면 반드시 부모의 오른쪽에 그려야 한다.
4. 트리의 루트가 있는 열에는 왼쪽 또는 오른쪽 서브트리에 속한 어떤 문자도 있어서는 안 된다.
5. 모든 노드에 대해, 그 노드의 왼쪽 서브트리 그림과 오른쪽 서브트리 그림은 어떤 열도 공유하지 않는다.

BST 전체를 그린 뒤, 행은 위에서 아래로 1부터, 열은 왼쪽에서 오른쪽으로 1부터 번호를 매긴다.

트리가 매우 커질 수 있어 그림이 너무 커지면 Z 교수가 전체를 일일이 확인하기 어렵다. 그래서 전체 그림 대신 그림의 조각 $m$개만 제출하면 된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 다음과 같이 구성된다.

• 양의 정수 $N$ ($N \le 100000$).
• 서로 다른 정수 $N$개. 각 정수는 32비트 부호 있는 정수로 표현할 수 있다. 이들을 주어진 순서대로 하나씩 빈 BST에 삽입한다.
• 정수 $M$ ($M \le 5$).
• 이어서 네 개의 정수로 이루어진 그룹이 $M$개 주어진다. 각 그룹은 요청한 조각의 왼쪽 위 모서리의 행과 열, 그리고 그 조각의 행 수 $R_i$와 열 수 $C_i$를 나타낸다. 입력의 모든 정수는 양수이며 32비트 부호 있는 정수 범위에 들어간다. 단, $R_i$와 $C_i$는 $0 < R_i \le 200$, $0 < C_i \le 200$을 만족한다.

각 테스트 케이스에 대해, 먼저 1부터 시작하는 케이스 번호를 Case #k: 형식으로 한 줄에 출력한다.

그다음 요청한 조각 $M$개를 출력한다. 각 조각은 최대 $R_i$개의 줄로 이루어지며(아래 참고), 출력하는 각 줄은 정확히 $C_i$개의 문자를 담는다. 빈 칸은 공백(ASCII 32)으로 채운다. 다만 공백만으로 이루어진 줄은 출력하지 않는다.

각 조각을 출력한 뒤에는 빈 줄을 하나 출력한다. 단, 마지막 테스트 케이스의 마지막 조각 뒤에는 빈 줄을 추가로 출력하지 않는다.