Перетин — об'єднання#7047

Перетин — об'єднання

18 секунд

32 мегабайти

Складна

На уроках математики Петрик ознайомився з такими поняттями:

перетином сукупності множин називають множину усіх тих елементів, що належать до усіх множин сукупності;
об'єднанням сукупності множин називають множину усіх тих елементів, що належать хоча б до однієї з множин сукупності.

Для того, щоб пересвідчитися, що учні добре засвоїли ці поняття й не плутають їх, учитель задав цілу низку задач як домашнє завдання.

Допоможіть Петрику автоматизувати процес виконання домашнього завдання, створивши програму, що знаходить перетин і об'єднання множин. При цьому кожна множина є або проміжком на дійсній прямій, або одноелементною множиною.

Вхідні дані

Перший рядок вхідного файлу містить одне натуральне число $n$ — кількість множин, для яких потрібно знайти перетин і об'єднання.

Усі наступні рядки описують набір тестів. Перед кожним тестом розташовано порожній рядок, а сам тест задано $n$ рядками, у кожному з яких записано:

або одноелементну множину таким чином:

"{"

десятковий запис натурального числа без коми чи крапки

"}".

або проміжок таким чином:

"[" або "("

десятковий запис лівого кінця проміжку без коми чи крапки

";"

десятковий запис правого кінця проміжку без коми чи крапки

")" або "]".

Квадратні дужки "[" або "]" вказують на включення відповідного кінця в проміжок. Круглі дужки "(" або ")" вказують на те, що відповідний кінець не включений у проміжок. Усі кінці проміжків і елементи усіх одноелементних множин є натуральними числами і не перевищують $3 (n + 4)$ 3(n + 4).

Останній рядок вхідного файлу порожній.

Передбачено перевірку для таких значень $n$ : $2$ , $8$ , $4000$ , $40000$ . Відповідні вхідні файли містять по $249$ , $249$ , $249$ і $261$ тестів, тобто по $749$ , $2243$ , $996251$ і $10440263$ рядків.

Вихідні дані

Вихідний файл складається з груп по $3$ рядки. Кількість груп така сама, як кількість тестів у вхідному файлі.

Перший рядок групи має містити традиційний запис (див. вимоги до вхідних даних) перетину множин, заданих відповідною групою у вхідному файлі. Якщо перетин порожній, то цей рядок має містити лише два символи "{}".

Другий рядок групи має містити традиційний запис об'єднання множин, заданих відповідною групою у вхідному файлі, з використанням великої літери латиниці «U» для позначення операції об'єднання. Це об'єднання потрібно подати як об'єднання проміжків і одноелементних множин таким чином:

об'єднання будь-яких двох проміжків або будь-якого проміжку та будь-якої одноелементної множини не є проміжком;
проміжки та одноелементні множини записані у порядку зростання на дійсній прямій, тобто у порядку зростання кінців проміжків та елементів одноелементних множин.

Третій рядок групи має бути порожнім.

Приклади

Приклад 1