Hide

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
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Greg Hamerly
Source Baylor University Introduction to Computation Theory
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in