Very Boring Homework#3089
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 hand in correct solutions. He believes this is not because the task is easy, but rather because the test data was too small. Therefore, he decides to assign the same homework again, but this time with enormous test cases. Of course, his students think this homework becomes even more boring now. They need your help again.
For those who do not recall the homework given by Prof. Z last time:
You are asked to draw the graph of a binary search tree (BST).
A binary search tree, sometimes 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 left and right subtrees must also be binary search trees.
Given a list of integer keys that should be inserted into the BST one by one in order, a unique BST is formed. Prof. Z wants the students to draw the graph of this BST.
The rules to draw the BST are as follows:
The graph of a -node BST is a single 'o' (15th small Latin letter).
If the BST has a non-empty subtree, draw a single '|' just above the subtree's root, and a single '+' just above the previous '|'. In the row with '+', use the minimal number (possibly ) of '-' to connect '+' (for the left or right subtree) and 'o' (the parent node of the subtrees).
The left subtree (if it exists) must be drawn to the left of its parent. Likewise, the right subtree (if it exists) must be drawn to the right of its parent.
The column of the BST's root must not have any character belonging to the left or right subtree.
For each node of the BST, the graph of its left subtree and the graph of its right subtree must not share any columns in the whole tree's picture.
After the entire BST is drawn, number the rows top-to-bottom from , and the columns left-to-right from .
Because the tree may be large, the drawing may be too big for Prof. Z to inspect completely. Therefore, you are only required to provide fragments of the graph for Prof. Z instead of the whole drawing.
The first line contains , the number of test cases. test cases follow.
For each test case:
The first line contains a positive integer (N \leq 100000).
The second line contains distinct integers, each representable as a -bit signed integer. Insert these into an empty BST one by one in the given order.
The third line contains an integer (M \leq 5).
lines follow, each containing four integers: the row and column numbers of the top-left corner, and the number of rows R_i and columns C_i of the required fragment, respectively. All input integers are positive and fit in a -bit signed integer. R_i and C_i are less than or equal to and greater than .
For each test case:
Output the case number (starting from ) in the first line.
Then print blocks. Each block contains R_i (or fewer, see below) lines. Each line must contain exactly C_i characters. Use space (ASCII ) to fill blank positions. If a line contains only spaces, do not output the line.
Output a blank line after each graph fragment.
Example 1