Дуже нудне домашнє завдання#3089
Професор Z вважає, що його домашнє завдання надто складне для більшості студентів (чи пам'ятаєте ви задачу "Нудне домашнє завдання"?). На свій подив, він отримує багато коректних розв'язків. Він думає, що причина не в легкості завдання, а в тому, що тестових даних було замало. Тому він вирішує дати те саме домашнє ще раз, але цього разу зі справді величезними тестами. Звісно, студентам це завдання здається ще більш нудним. Вони знову потребують вашої допомоги.
Для тих, хто не пам'ятає попереднє домашнє від професора Z:
Вам треба намалювати графік бінарного дерева пошуку (BST).
Бінарне дерево пошуку — це бінарне дерево, у якого для кожного вузла виконуються такі властивості: ліве піддерево містить тільки вузли з ключами меншими, ніж у цього вузла; праве піддерево — тільки вузли з ключами більшими, ніж у цього вузла. Обидва піддерева теж повинні бути бінарними деревами пошуку.
Дано список цілих ключів, які треба вставити у BST по черзі. В результаті утворюється єдине BST. Професор Z хоче, щоб студенти намалювали графік цього BST.
Правила малювання BST такі:
Графік BST з вузлом — це одна 'o' (15-та маленька латинська літера).
Якщо у BST є непорожнє піддерево, малюють одну '|', розташовану безпосередньо над коренем піддерева, і одну '+', розташовану безпосередньо над попередньою '|'. У рядку з '+', мінімальною кількістю (можливо 0) символів '-' з'єднують '+' (для лівого чи правого піддерева) та 'o' (вузол-батько піддерева).
Ліве піддерево (якщо існує) має бути намальоване ліворуч від батьківського вузла. Аналогічно, праве піддерево — праворуч від батьківського.
У колонці, де розташований корінь BST, не повинно бути символів від лівого чи правого піддерева.
Для кожного вузла BST графіки його лівого та правого піддерева не повинні перетинатися по жодній колонці у всьому зображенні дерева.
Після побудови всього BST, пронумеруйте рядки зверху вниз з , а стовпці — зліва направо з .
Оскільки дерево може бути дуже великим, графік може вийти занадто великим для повної перевірки професором Z. Тому вам потрібно надати не весь малюнок, а лише фрагментів згідно з вимогою професора Z.
Перший рядок містить — кількість тестів. Далі йдуть тестів.
Для кожного тесту:
Перший рядок містить одне додатне ціле (N \leq 100000).
Другий рядок містить різних цілих чисел, кожне з яких вміщується у -бітне знакове ціле. Вставляйте їх у порожнє BST по порядку.
Третій рядок містить одне число (M \leq 5).
Далі йде рядків, кожен містить чотири цілі числа: номер рядка і стовпця лівого верхнього кута фрагменту, а також кількість рядків R_i та стовпців C_i у потрібному фрагменті відповідно. Всі числа — додатні і вміщаються у -бітне знакове ціле. R_i та C_i не перевищують і більші за .
Для кожного тесту:
Виведіть у першому рядку номер тесту (починаючи з ).
Далі виведіть блоків. Кожен блок містить R_i (або менше, див. нижче) рядків. У кожному рядку має бути рівно C_i символів. Порожні позиції заповнюйте пробілом (ASCII ). Якщо рядок складається тільки з пробілів — не виводьте цей рядок.
Між фрагментами виводьте один порожній рядок.
Приклад 1