题解

这道题目的核心思想是根据用户搜索过的关键词,对商品进行排序,使得包含更多用户搜索过关键词的商品排在前面。

具体解题步骤如下:

1. 读入用户搜索过的关键词,存储在集合 k 中,方便快速判断一个关键词是否被用户搜索过。
2. 对于每个商品,统计它包含的关键词中有多少个是用户搜索过的,记为 c。将 c 和商品编号 i 作为一个二元组 {c, i} 存储在 res 中。
3. 对 res 按照自定义的比较函数进行排序,优先按照 c 值降序排列,如果 c 值相同,则按照编号升序排列。
4. 遍历排序后的 res ,根据编号输出对应的商品名称。

题目描述

小红需要设计一套推荐算法。 该算法的核心思想如下，首先给定一个商品清单，其中有每个商品所包含的关键词属性，然后给出用户最近搜索过的一些关键词，请你将包含用户搜索过的更多的关键词的商品排在用户目录的前面。

如果两个商品关键词数量相同，则按商品出现的顺序排序。

输入描述

第一行输入一个正整数$n,q$，代表商品数量、用户搜索的关键词数量。

第二行输入$q$个互不相同的、仅由小写文母组成的字符串，代表用户搜索过的关键词。

接下来的$2*n$行，每两行描述一个商品。

第一行输入一个仅由小写字母组成的字符围name和一个正整数$m_i$，代表商品的名称和商品包含的关键词属性数量。

第二行输入$m_i$个互不相同的、仅由小写字母组成的字符串，代表每个商品的属性。

$1≤ n,q < 30000$

所有的$m_i$之和不超过30000 保证所有字符串长度不超过 20，所有商品的名称互不相同。

输出描述

按照题意顺序输出商品

样例

输入

2 5
red book game music sigma
mozart 3
book classic music
arcaea 4
red music game hard

输出

arcaea
mozart