Очень скучное домашнее задание
Профессор Z считает, что его домашнее задание слишком сложное для большинства студентов (помните задачу "Скучное домашнее задание"?). К его удивлению, многие студенты сдают правильные решения. Он полагает, что это связано с небольшим размером набора данных, который он использовал для тестирования программ студентов, а не с низкой сложностью задания. Поэтому он решает снова дать студентам то же домашнее задание, но с огромными тестовыми случаями. Конечно, студенты считают, что его домашнее задание стало еще более скучным. Им снова нужна ваша помощь.
Для тех, кто не знает, какое домашнее задание профессор Z дал своим студентам в прошлый раз:
Вам нужно нарисовать график бинарного дерева поиска (BST).
Бинарное дерево поиска, также известное как упорядоченное или отсортированное бинарное дерево, — это структура данных на основе узлов, обладающая следующими свойствами: Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла. Правое поддерево узла содержит только узлы с ключами, большими, чем ключ узла. И левое, и правое поддеревья также должны быть бинарными деревьями поиска.
из Википедии
Дан список целочисленных ключей, которые должны быть вставлены в BST по одному в заданном порядке, мы можем сформировать уникальное BST. Более того, профессор Z хочет, чтобы студенты нарисовали график этого BST.
Правила для рисования графика BST перечислены ниже:
График BST с одним узлом — это одиночная 'o' (15-я маленькая латинская буква).
Если у BST есть непустое поддерево, нарисуйте одиночную '|' прямо над корнем поддерева и одиночный '+' прямо над ранее нарисованной '|'. Наконец, в строке с '+', используйте минимальное количество (включая 0) '-' для соединения '+' (соответствующего левому или правому поддереву) и 'o' (обозначающего родительский узел поддеревьев).
Левое поддерево (если существует) должно быть нарисовано слева от своего родителя. Аналогично, правое поддерево (если существует) должно быть нарисовано справа от своего родителя.
Столбец корня BST не должен содержать символов, принадлежащих левому или правому поддереву.
Для каждого узла BST график его левого поддерева и график его правого поддерева не должны иметь общих столбцов в изображении всего дерева.
После того, как все BST будет нарисовано, мы нумеруем строки сверху вниз, начиная с 1, и также нумеруем столбцы слева направо, начиная с 1.
Из-за большого масштаба дерева график станет настолько большим, что профессор Z не сможет проверить каждую деталь графика на этот раз. Поэтому вас просят сдать профессору Z только m фрагментов этого графика вместо всего графика.
Входные данные
Первая строка содержит T, количество тестовых случаев. Следуют T тестовых случаев.
Для каждого тестового случая:
Первая строка содержит положительное целое число N (N ≤ 100000).
Вторая строка содержит N различных целых чисел, каждое из которых может быть представлено 32-битным знаковым целым числом. Эти числа должны быть вставлены в пустое BST по одному в заданном порядке.
Третья строка содержит целое число M (M ≤ 5).
Следуют M строк, каждая из которых содержит четыре целых числа, которые являются номером строки и столбца верхнего левого угла, и количеством строк R_i и столбцов C_i требуемого фрагмента графика соответственно. Все входные целые числа будут положительными и поместятся в 32-битное знаковое целое число, за исключением R_i и C_i, которые будут меньше или равны 200 и больше 0.
Выходные данные
Для каждого тестового случая:
Выведите номер случая, начиная с 1, в первой строке.
Затем следуют M блоков, каждый из которых содержит R_i (или меньше, см. далее) строк. Каждая строка должна содержать ровно C_i символов. Используйте пробел (ASCII 32) для заполнения пустых мест. Но если строка содержит только пробелы, эта строка не должна выводиться.
Выведите пустую строку после каждого фрагмента графика.