Description

Inspired by the classic problem “Trees Outside the School Gate”, person A, based on basic knowledge of discrete mathematics, abstracts $5$ kinds of operations to maintain a set $S$ ($S$ is initially empty) and finally output $S$. Now, please complete this harder enhanced version of “Trees Outside the School Gate” — “Intervals Outside the School Gate”.

The five operations are:

• U T: $S = S \cup T$
• I T: $S = S \cap T$
• D T: $S = S - T$
• C T: $S = T - S$
• S T: $S = S \oplus T$

The basic set operations are defined as follows:

• $A \cup B$: $\{x \mid x \in A \vee x \in B\}$
• $A \cap B$: $\{x \mid x \in A \wedge x \in B\}$
• $A - B$: $\{x \mid x \in A \wedge x \notin B\}$
• $A \oplus B$: $(A-B)\cup (B-A)$.

Input Format

There are $M$ lines. The first letter of each line describes the operation type, followed by an interval (an interval is written as (a,b), (a,b], [a,b), [a,b]).

Output Format

Output one line containing several intervals representing the set $S$. All intervals should be output in increasing order, and there should be exactly one space between two adjacent intervals.

If the set is empty, output empty set.

U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]

(2,3)

Hint

$0 \leq a,b \leq 65535, M \leq 70000$.

Translated by ChatGPT 5