Very Boring Homework

Prof. Z thinks his homework is very hard for most of his students to solve (do you remember the task "Boring Homework"?). To his surprise, many students still hand in correct solutions. He believes the real reason is the small size of the data set he used to test the students' programs, not the low difficulty of the task. So he decides to assign the same homework again, this time with enormous test cases. Naturally, his students find the homework even more boring now, and they need your help again.

For those who do not know what homework Prof. Z gave last time:

You are asked to draw the graph of a binary search tree (BST).

A binary search tree, sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure with 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

Given a list of integer keys inserted into the BST one by one in order, we obtain a unique BST. Prof. Z wants the students to draw the graph of this BST.

The rules for drawing the graph of a BST are as follows:

1. The graph of a single-node BST is one o (the 15th lowercase Latin letter).
2. If a node has a non-empty subtree, draw one | directly above that subtree's root, and one + directly above that |. Then, in the row that contains the +, use the fewest possible - characters (possibly none) to connect that + (which sits above the left or right subtree) to the o of the parent node.
3. A left subtree, if it exists, must be drawn on the left side of its parent; a right subtree, if it exists, must be drawn on the right side of its parent.
4. The column of the tree's root must not contain any character that belongs to the left or right subtree.
5. For every node, the graph of its left subtree and the graph of its right subtree never share a column.

After the whole BST has been drawn, number the rows from top to bottom starting at 1, and number the columns from left to right starting at 1.

Because the tree can be huge, the graph becomes far too large for Prof. Z to check in full. So you only have to submit $m$ fragments of the graph instead of the whole picture.

The first line contains $T$, the number of test cases. $T$ test cases follow.

For each test case:

• A positive integer $N$ ($N \le 100000$).
• $N$ distinct integers, each representable as a 32-bit signed integer. They are inserted into an empty BST one by one, in the given order.
• An integer $M$ ($M \le 5$).
• $M$ groups of four integers follow. Each group gives the row and column of the top-left corner of a requested fragment, followed by its number of rows $R_i$ and number of columns $C_i$. Every input integer is positive and fits in a 32-bit signed integer, except $R_i$ and $C_i$, which satisfy $0 < R_i \le 200$ and $0 < C_i \le 200$.

For each test case, first print the case number (counting from 1) on its own line in the form Case #k:.

Then print the $M$ requested fragments. Each fragment has at most $R_i$ lines (see below), and every printed line contains exactly $C_i$ characters, using spaces (ASCII 32) to fill empty cells. However, a line consisting only of spaces is not printed.

Print one blank line after each graph fragment, but do not print an extra blank line after the final fragment of the final test case.