Choosing Pizza Toppings

Time limit1sMemory limit256 MB

Summary

Simulate the given repair loop that flips one unfulfilled topping of the first unhappy friend until every friend has more than a third of wishes met.

Level: Easy3 of 10
Topics: Simulation, Implementation, Sorting
Solved: No attempts yet

Problem

My friends and I are ordering one big pizza to share. Choosing what goes on it is not simple, because everyone wants something different. Gunnar wants bananas, Emma wants no bananas but does want olives, Marc insists on tomatoes, and so it goes.

Once we managed to find a set of toppings that fulfilled at least 2/3 of the wishes of every one of us, and we agreed that this was good enough. Then Lukas lost the note with that list on the way to the pizzeria, so we have to choose again. This time we lower the bar and look for a set of toppings that fulfils strictly more than 1/3 of the wishes of every friend.

Input

The first line contains an integer $N$ ( $1 \le N \le 10000$ ), the number of friends in the group, myself included. Each of the next $N$ lines describes one friend. Such a line starts with an integer $w$ ( $1 \le w \le 30$ ), the number of wishes of that friend, followed by $w$ wishes separated by spaces. A wish is written as +topping or -topping. The wish +topping means the friend wants that topping on the pizza, and -topping means the friend wants it left off. Inside one line a topping name appears at most once.

A topping name is a string of 1 to 15 lowercase English letters. The input mentions at most 250 different toppings.

Output

The wish +topping is fulfilled when that topping is on the pizza, and the wish -topping is fulfilled when that topping is not on the pizza. A friend who has $w$ wishes and $f$ fulfilled wishes is happy when $3f > w$ .

Print a set of toppings that makes every friend happy. You may assume that some set of toppings fulfils at least 2/3 of the wishes of every friend. Many sets can make everyone happy, so print exactly the set that the procedure below builds.

Number the friends 1 to $N$ in input order. Start with no topping on the pizza and with $r = 1$ , then repeat the following.

If every friend is happy, stop.
Otherwise let $i$ be the smallest number of a friend who is not happy. List the wishes of friend $i$ that are not fulfilled, sorted by topping name in increasing order. Call this list $L$ and its length $u$ .
Replace $r$ by $(48271 \times r) \bmod 2147483647$ , then set $k = r \bmod u$ .
Fulfil the wish at position $k$ of $L$ , counting positions from 0. Put its topping on the pizza if the wish is a + wish, and take its topping off the pizza if the wish is a - wish.

When the procedure stops, print the toppings that are on the pizza in lexicographic order, one per line. Every printed topping appears in the input, and no topping is printed twice.

Examples4

Example 1

Input

1
4 +zucchini +mozzarella +mushrooms -artichoke

Expected output

mushrooms

Example 2

Input

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

Expected output

bluecheese
redbeans
soylentgreen

Example 3
Input
```
1
1 +pineapple
```
Expected output
```
pineapple
```

Example 4

Input

5
1 +ham
2 +ham -olive
3 -corn +basil -olive
3 +ham +corn -olive
6 +ham +basil +corn -olive -tuna +egg

Expected output

ham