我和朋友们正在订购一个大披萨来分享。你可以想象这相当复杂,因为每个人对披萨上应该放什么都有不同的愿望。例如,Gunnar 想要披萨上有香蕉,Emma 不想要香蕉但想要橄榄,Marc 想要有番茄,等等。幸运的是,我们克服了重重困难,成功选出了一套配料,使得每个人的愿望都至少有 $2/3$ 得到了满足,我们一致认为这已经足够好了。
但随后,灾难降临了!我们派 Lukáš 去买披萨,但他不小心弄丢了写着我们精心挑选的配料清单的那张纸。现在我们回到了原点,必须重新制定一份配料清单。考虑到我们当初找到最初那份配料清单花了多长时间,我们决定降低一点标准,只求找到一份清单,使得每个人的愿望都有严格超过 $1/3$ 得到满足。
你能帮帮我们吗?如果你能做到,你就能吃到披萨了!
照片由 Sam DeLong 提供
输入格式
输入的第一行包含一个整数 $1 \le N \le 10\,000$,表示小组中的朋友人数(包括你自己)。接下来的 $N$ 行,每行包含其中一位朋友的愿望清单。该清单以一个整数 $1 \le w \le 30$ 开头,表示该朋友拥有的愿望数量,随后是空格分隔的愿望列表。每个愿望要么是 “+
配料名称是由最多 15 个小写英文字母 ‘a’-‘z’ 组成的非空字符串。最多有 250 种不同的配料。
输出格式
输出一份配料清单(不重复,用空格或换行符分隔),使得每个朋友都有严格超过 $1/3$ 的愿望得到满足。你可以假设存在一份清单,使得每个朋友至少有 $2/3$ 的愿望得到满足。
你的配料清单中不得包含输入中未提及的配料,也不允许包含重复项。
样例
样例输入 1
1 4 +zucchini +mozzarella +mushrooms -artichoke
样例输出 1
zucchini mozzarella mushrooms artichoke
样例输入 2
3 3 +redbeans +soylentgreen -bluecheese 3 +redbeans -soylentgreen +bluecheese 3 -redbeans +soylentgreen +bluecheese
样例输出 2
redbeans soylentgreen bluecheese