描述

联邦调查局（FBI）正在对一个已知的犯罪分子藏身之处进行监视，这个地方是许多心怀恶意的男男女女的通讯中心。通过复杂的解密软件以及传统的窃听手段，他们能够解码从该地点发出的任何电子邮件信息。然而，在签发任何逮捕令之前，他们必须将实际的姓名与信息中的用户 ID 进行匹配。这些犯罪分子虽然邪恶，但并不愚蠢，所以他们使用由字母组成的随机字符串作为他们的用户 ID（在这里不会发现类似 dillingerj 这样明显的 ID）。联邦调查局知道每个犯罪分子只使用一个 ID。他们拥有的唯一其他有助于匹配的信息是进出该藏身之处的人员姓名记录。在许多情况下，这些信息足以将姓名与 ID 联系起来。

输入

输入由一个问题实例组成。第一行包含一个正整数 \(n\)，表示使用该藏身之处的犯罪分子数量，\(n\) 的最大值为 \(20\)。下一行包含 \(n\) 个用户 ID，用单个空格分隔。接下来是按时间顺序排列的记录条目。每个记录条目具有类型 type 和参数 arg 的形式，其中 type 为 E、L 或 M：E 表示犯罪分子 arg 进入了藏身之处；L 表示犯罪分子 arg 离开了藏身之处；M 表示截获了来自用户 ID 为 arg 的信息。包含单个字母 Q 的一行表示记录结束。请注意，并非所有用户 ID 都会出现在记录中，但每个犯罪分子的姓名至少会在记录中出现一次。在记录开始时，假定藏身之处是空的。所有姓名和用户 ID 都仅由小写字母组成，长度最多为 \(20\)。注意：包含用户 ID 的那一行可能包含超过 \(80\) 个字符。

输出

输出由 \(n\) 行组成，每行包含一个犯罪分子姓名及其对应的用户 ID（如果已知）。列表应按犯罪分子姓名的字母顺序排序。每行的形式为 name:userid，其中 name 是犯罪分子的姓名，userid 要么是他们的用户 ID，要么是字符串 ???（如果根据监视记录无法确定他们的用户 ID）。

7 
bigman mangler sinbad fatman bigcheese frenchie capodicapo 
E mugsy 
E knuckles 
M bigman 
M mangler 
L mugsy 
E clyde 
E bonnie 
M bigman 
M fatman 
M frenchie 
L clyde 
M fatman 
E ugati 
M sinbad 
E moriarty 
E booth 
Q 

bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad

来源

2001 年中北美东部地区竞赛