Дуже нудне домашнє завдання
Професор З вважає, що його домашнє завдання занадто складне для більшості студентів (пам'ятаєте завдання "Нудне Домашнє Завдання"?). На його здивування, багато студентів здають правильні рішення. Він припускає, що це через невеликий розмір набору даних, який він використовував для тестування програм студентів, а не через низьку складність завдання. Тому він вирішує дати студентам те саме завдання знову, але з великими тестовими випадками. Звісно, студенти вважають, що його завдання стало ще нуднішим цього разу. Вони знову потребують вашої допомоги.
Для тих, хто не знає, яке домашнє завдання дав Професор З своїм студентам минулого разу:
Вам потрібно намалювати графік бінарного дерева пошуку (BST).
Бінарне дерево пошуку, яке іноді також називають впорядкованим або відсортованим бінарним деревом, є структурою даних на основі вузлів, яка має такі властивості: Ліве піддерево вузла містить лише вузли з ключами, меншими за ключ вузла. Праве піддерево вузла містить лише вузли з ключами, більшими за ключ вузла. Обидва ліве і праве піддерева також повинні бути бінарними деревами пошуку.
з Вікіпедії
Дано список цілих чисел, які повинні бути вставлені в BST по черзі, ми можемо сформувати унікальне BST. Більше того, Професор З хоче, щоб студенти намалювали графік цього BST.
Правила для малювання графіка BST наведені нижче:
Графік BST з 1 вузлом - це один 'o' (15-та мала латинська літера).
Якщо BST має непорожнє піддерево, намалюйте один '|' прямо над коренем піддерева, і один '+' прямо над попередньо намальованим '|'. Нарешті, в рядку з '+', використовуйте найменшу кількість (включаючи 0) '-' для з'єднання '+' (відповідно до лівого або правого піддерева) і 'o' (що позначає батьківський вузол піддерев).
Ліве піддерево (якщо існує) повинно бути намальоване з лівого боку від свого батька. Аналогічно, праве піддерево (якщо існує) повинно бути намальоване з правого боку від свого батька.
Колонка кореня BST не повинна містити жодних символів, що належать до лівого або правого піддерева.
Для кожного вузла BST графік його лівого піддерева і графік його правого піддерева не повинні мати спільних колонок на зображенні всього дерева.
Після того, як все BST було намальовано, ми нумеруємо рядки зверху вниз, починаючи з 1, і так само колонки зліва направо, починаючи з 1.
Через великий масштаб дерева графік стане настільки великим, що Професор З не зможе перевірити кожну деталь графіка цього разу. Тому вас просять здати лише 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) для заповнення порожніх місць. Але якщо строка містить лише пробіли, ця строка не повинна бути виведена.
Виведіть порожню строку після кожного фрагмента графіка.