Intersection — union
In math class, Petryk learned the following concepts:
The intersection of a collection of sets is the set of all elements that are common to all sets in the collection.
The union of a collection of sets is the set of all elements that belong to at least one of the sets in the collection.
To ensure students fully grasp these concepts and avoid confusion, the teacher assigned a series of problems as homework.
Help Petryk automate his homework by creating a program that calculates the intersection and union of sets. Each set is either an interval on the real line or a singleton set.
Input
The first line of the input file contains a single natural number n — the number of sets for which the intersection and union need to be determined.
All subsequent lines describe a series of tests. Before each test, there is a blank line, and the test itself consists of n lines, each containing:
either a singleton set formatted as:
"{"
a decimal representation of a natural number without a comma or period
"}".
or an interval formatted as:
"[" or "("
a decimal representation of the left endpoint of the interval without a comma or period
";"
a decimal representation of the right endpoint of the interval without a comma or period
")" or "]".
Square brackets "[" or "]" indicate that the corresponding endpoint is included in the interval. Round brackets "(" or ")" indicate that the corresponding endpoint is not included in the interval. All endpoints of intervals and elements of all singleton sets are natural numbers and do not exceed 3(n+4).
The last line of the input file is blank.
Tests are provided for the following values of n: 2, 8, 4000, 40000. The corresponding input files contain 249, 249, 249, and 261 tests, i.e., 749, 2243, 996251, and 10440263 lines.
Output
The output file consists of groups of 3 lines. The number of groups matches the number of tests in the input file.
The first line of each group should contain the traditional notation (as per input data requirements) of the intersection of the sets given by the corresponding group in the input file. If the intersection is empty, this line should contain only the two characters "{}".
The second line of each group should contain the traditional notation of the union of the sets given by the corresponding group in the input file, using the capital Latin letter "U" to denote the union operation. This union should be presented as a union of intervals and singleton sets in the following way:
the union of any two intervals or any interval and any singleton set is not an interval;
intervals and singleton sets are recorded in the order of increasing endpoints of intervals and elements of singleton sets, i.e., in the order of movement in the positive direction of the real line.
The third line of each group should be blank.