Problem D
Set operations
A mathematical set is a collection of distinct objects. We write $x \in A$ if object $x$ is a member of set $A$. Given two sets $A$ and $B$, some basic operations we can perform on them are:
-
Union: $A \bigcup B = \{ x~ |~ x \in A \mbox{ or } x \in B\} $
-
Intersection: $A \bigcap B = \{ x~ |~ x \in A \mbox{ and } x \in B\} $
-
Cartesian product: $A \times B = \{ (x, y)~ |~ x \in A \mbox{ and } y \in B\} $
For this problem, you are given two sets of strings, $A$ and $B$. Produce the union, intersection, and cartesian product of these sets.
Input
Input has two descriptions of sets of strings, one after the other. Each set begins with a line containing an integer $0 \le n \le 100$. The following $n$ lines contain $n$ distinct strings. Each string is made up of $1$ to $10$ lowercase letters (a–z).
Output
Give the output in three groups: the union, then the intersection, then the cartesian product of the two sets. Give one element of the set per line. Within each group, order the lines lexicographically (alphabetically, shorter strings first).
| Sample Input 1 | Sample Output 1 |
|---|---|
5 dog frog cat house cats 3 apple pear house |
apple cat cats dog frog house pear house cat apple cat house cat pear cats apple cats house cats pear dog apple dog house dog pear frog apple frog house frog pear house apple house house house pear |
