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

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

• перетином сукупності множин називають множину усіх тих елементів, що належать до усіх множин сукупності;

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

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

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

Вхідні дані

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

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

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

"{"

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

"}".

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

"[" або "("

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

";"

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

")" або "]".

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

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

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

Вихідні дані

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

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

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

• об’єднання довільних двох проміжків або довільного проміжку й довільної одно­еле­мент­ної множини не є проміжком;

• проміжки та одноелементні множини записано у порядку руху у додатному напрямі дійсної прямої, тобто у порядку зростання кінців проміжків та елементів одно­елемент­них множин.

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

Приклади