BWORK - Boring Homework

Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game "Starcraft II" that she can't finish her homework in time. She needs your help.

 A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

--from Wikipedia 

To draw a picture of BST, you may follow the rules listed below: 

  1. The picture of a 1-node BST, whose size is 1*1, is a single 'o' (15th small Latin letter).
  2. If a BST has a non-empty subtree, draw a single '|' just above the subtree's root, and a single '+' just above previous drawn '|'. Finally, in the row of '+', use the least number (including 0) of '-'s to connect '+' (denoting the left subtree and right subtree) and 'o' (denoting the parent node of the subtree)
  3. The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
  4. The column of the BST's root must not contain any character from left subtree or right subtree.
  5. Any column containing any characters from BST's left subtree must not contain any characters from BST's right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.

 The sample output may give a clear clarification about the format of the picture.

Input

The first line contains T (T <= 2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.

Output

For each test case:

Output the case number counting from 1 in the first line. The next lines should be the image described above without any trailing spaces. See the sample for more format details.

Notice that no trailing whitespaces after the last visible characters of each line are allowed.

Example

Input:
3
3 3 1 2
6 4 5 6 1 3 2
5 3 4 5 2 1

Output:
Case #1:
+-o
|
o+
 |
 o
Case #2:
+--o+
|   |
o-+ o+
  |  |
 +o  o
 |
 o
Case #3:
 +o+
 | |
+o o+
|   |
o   o

Added by:Fudan University Problem Setters
Date:2011-05-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Fudan University Local Contest #2, by Blue Mary

hide comments
2021-09-24 01:44:28 David
Ensure your solution does not have spaces at the end of any line. The end of each line is a non-space character.
2016-11-18 09:02:55
Fantastic graphic problem :)
2011-07-19 06:13:35 Hagen von Eitzen
I have no idea why I keep getting WA

EDIT: Ah, there are nontrivial places where trailing spaces can lurk :)

Last edit: 2011-07-19 20:05:30
2011-05-19 12:00:17 :D
There should be a newline at the end of last line (after last non-white character).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.