Пересечение — объединение
На уроках математики Петрик познакомился с такими понятиями:
пересечение совокупности множеств — это множество всех элементов, которые принадлежат всем множествам совокупности;
объединение совокупности множеств — это множество всех элементов, которые принадлежат хотя бы одному из множеств совокупности.
Чтобы убедиться, что ученики хорошо усвоили эти понятия и не путают их, учитель задал целый ряд задач в качестве домашнего задания.
Помогите Петрику автоматизировать выполнение домашнего задания, создав программу, которая находит пересечение и объединение множеств. Каждое множество представлено либо как промежуток на числовой прямой, либо как одноэлементное множество.
Входные данные
Первая строка входного файла содержит одно натуральное число n — количество множеств, для которых нужно найти пересечение и объединение.
Все последующие строки описывают набор тестов. Перед каждым тестом расположен пустой рядок, а сам тест задан n строками, в каждой из которых записано:
либо одноэлементное множество в виде:
"{"
десятичная запись натурального числа без запятой или точки
"}".
либо промежуток в виде:
"[" или "("
десятичная запись левого конца промежутка без запятой или точки
";"
десятичная запись правого конца промежутка без запятой или точки
")" или "]".
Квадратные скобки "[" или "]" указывают на включение соответствующего конца в промежуток. Круглые скобки "(" или ")" указывают на то, что соответствующий конец не включен в промежуток. Все концы промежутков и элементы всех одноэлементных множеств являются натуральными числами и не превышают 3(n+4).
Последняя строка входного файла пустая.
Предусмотрена проверка для таких значений n: 2, 8, 4000, 40000. Соответствующие входные файлы содержат по 249, 249, 249 и 261 тестов, то есть по 749, 2243, 996251 и 10440263 строк.
Выходные данные
Выходной файл состоит из групп по 3 строки. Количество групп такое же, как количество тестов во входном файле.
Первая строка группы должна содержать традиционную запись (см. требования к входным данным) пересечения множеств, заданных соответствующей группой входного файла. Если пересечение пустое, то эта строка содержит только два символа "{}".
Вторая строка группы должна содержать традиционную запись объединения множеств, заданных соответствующей группой входного файла, с использованием большой буквы латиницы «U» для обозначения операции объединения. Это объединение нужно представить как объединение промежутков и одноэлементных множеств следующим образом:
объединение любых двух промежутков или любого промежутка и любого одноэлементного множества не является промежутком;
промежутки и одноэлементные множества записаны в порядке возрастания на числовой прямой, то есть в порядке увеличения концов промежутков и элементов одноэлементных множеств.
Третья строка группы должна быть пустой.