Pizza Problems

Photo by Sam DeLong

Me and my friends are ordering a big pizza to share. As you can imagine this is quite complicated, since everyone has different wishes about what should be on the pizza. For instance Gunnar wants bananas on the pizza, Emma doesn’t want bananas but wants olives, Marc wants there to be tomatoes, and so on. Fortunately, against all odds, we managed to come up with a selection of toppings such that everyone had at least $2/3$’s of their wishes fulfilled, which we unanimously decided was good enough.

But then, disaster struck! We sent out Lukáš to buy the
pizza, but he accidentally lost the piece of paper on which we
had written down our carefully selected list of toppings. Now
we’re back at square one, and have to construct a new selection
of toppings. Given how long it took us to find the original
selection of toppings, we have decided to lower our standards a
bit and just try to find a selection such that everyone has
*strictly* more than $1/3$ of their wishes fulfilled.

Can you help us with this? If you do, you’ll get some pizza!

The first line of input contains an integer $1 \le N \le 10\, 000$, the number of
friends in the group (including yourself). Each of the next
$n$ lines contains the
list of wishes of one of the friends. This list starts with an
integer $1 \le w \le 30$,
the number of wishes this friend has, followed by a
space-separated list of wishes. Each wish is either “`+<topping>`” or “`-<topping>`” where `<topping>` is the name of a topping,
indicating that this friend wants or does not want this
topping. Each topping name appears at most once in each
list.

Topping names are non-empty strings of up to $15$ lower-case English letters
‘`a`’-‘`z`’.
There are at most $250$
different toppings.

Output a list of toppings (without repetitions, separated by spaces or newlines) such that each friend has strictly more than $1/3$ of their wishes fulfilled. You may assume that there exists a list such that every friend has at least $2/3$ of their wishes fulfilled.

Your list of toppings is not allowed to contain any toppings that are not mentioned in the input, nor is it allowed to contain repetitions.

Sample Input 1 | Sample Output 1 |
---|---|

1 4 +zucchini +mozzarella +mushrooms -artichoke |
zucchini mozzarella mushrooms artichoke |

Sample Input 2 | Sample Output 2 |
---|---|

3 3 +redbeans +soylentgreen -bluecheese 3 +redbeans -soylentgreen +bluecheese 3 -redbeans +soylentgreen +bluecheese |
redbeans soylentgreen bluecheese |