Задачі
Перетин — об`єднання
Перетин — об`єднання
На уроках математики Петрик ознайомився з такими поняттями:
\begin{itemize}
\item \textit{перетином} сукупності множин називають множину усіх тих елементів, що належать до усіх множин сукупності;
\item \textit{об’єднанням} сукупності множин називають множину усіх тих елементів, що належать хоча б до однієї з множин сукупності.
\end{itemize}
Для того, щоб пересвідчитися, що учні добре засвоїли ці поняття й не плутають їх, учитель задав цілу низку задач як домашнє завдання.
Допоможіть Петрику автоматизувати процес виконання домашнього завдання, створивши програму, що знаходить перетин й об’єднання множин. При цьому кожна множина є або проміжком дійсної прямої, або одноелементною множиною.
\InputFile
\textit{Перший} рядок вхідного файлу містить одне натуральне число \textit{n} --- кількість множин, для яких потрібно знайти перетин і об’єднання.
Усі наступні рядки описують набір тестів. Перед кожним тестом розташовано порожній рядок, а сам тест задано\textbf{n} рядками, в кожному з яких записано:
\begin{itemize}
\item або одноелементну множину таким чином:
\end{itemize}
"\{"
десятковий запис натурального числа без коми чи крапки
"\}".
\begin{itemize}
\item або проміжок таким чином:
\end{itemize}
"\[" або "("
десятковий запис лівого кінця проміжку без коми чи крапки
";"
десятковий запис правого кінця проміжку без коми чи крапки
")" або "\]".
Квадратні дужки "\[" або "\]" вказують на належність відповідного кінця до проміжку. Круглі дужки "(" або ")" вказують на те, що відповідний кінець не належить до проміжку. Усі кінці проміжків і елементи усіх одноелементних множин натуральні й не перевищують \textbf{3(n+4)}.
Останній рядок вхідного файлу порожній.
Передбачено перевірку для таких величин \textbf{n}: \textbf{2}, \textbf{8}, \textbf{4000}, \textbf{40000}. Відповідні вхідні файли містять по \textbf{249}, \textbf{249},\textbf{249} і \textbf{261} тестів, тобто по \textbf{749}, \textbf{2243}, \textbf{996251} і \textbf{10440263} рядків.
\OutputFile
Вихідний файл складається з груп по \textbf{3} рядки. Кількість груп така сама, як кількість тестів у вхідному файлі.
\textit{Перший} рядок групи має містити традиційний запис (див. вимоги до вхідних даних) перетину множин, заданих відповідною групою вхідного файлу. Якщо перетин порожній, то цей рядок містить лише два символи "\{\}".
\textit{Другий} рядок групи має містити традиційний запис \textit{об’єднання} множин, заданих відповідною групою вхідного файлу, з використанням великої літери латиниці <<U>> для позначення операції об\textit{’}єднання. Це об’єднання потрібно подати об’єднанням проміжків і одноелементних множин таким чином:
\begin{itemize}
\item об’єднання довільних двох проміжків або довільного проміжку й довільної одноелементної множини не є проміжком;
\item проміжки та одноелементні множини записано у порядку руху у додатному напрямі дійсної прямої, тобто у порядку зростання кінців проміжків та елементів одноелементних множин.
\end{itemize}
\textit{Третій} рядок групи має бути порожнім.
Вхідні дані #1
2 [14;15) (11;14) [4;5) {4} [2;4) (3;7)
Вихідні дані #1
{} (11;15) {4} [4;5) (3;4) [2;7)