#4949. [Wf2017]Get a Clue!

内存限制:512 MiB 时间限制:15 Sec

题目描述

起源于19世纪40年代的英国的游戏Cluedo是世界上最流行的图版游戏之一。游戏的目标是找出谋杀 Boddy 先生的
凶手,凶手使用的凶器,以及行凶的地点。游戏使用一系列卡片表示六个角色 (标号A, B, · · · , F) 、六种武
器 (标号 G, H, · · · , L) 和九个房间 (标号 M, N, · · · , U) 。在游戏的开始,角色、武器和房间分
别会有一张卡片在玩家不知道的情况下被随机移除,它们分别表示凶手、凶器和作案地点。剩下的18张卡片会重新
排列并分发给玩家,第一张会给玩家1,接下来会给他右边的玩家2,依次类推。一些玩家可能比其他玩家多拿一张牌
。由于这道题的原因,玩家的数量为四个,这意味着玩家4 的右边是玩家1。游戏剩下的部分便是寻找线索。玩家轮
流决策,从玩家1开始,然后依次是其右边的玩家。每轮决策需要提出一个suggestion(即提议,包括指定嫌疑人、凶
器和作案地点) 并轮询其他玩家是否有证据能反对这个提议。例如,你可以对另一个玩家说: "我认为凶手是角色A,
凶器是L,作案房间是T。"如果其他玩家恰好有其中一张卡片,这个玩家必须向你 (且只有你) 展示这张卡片。如果
他有多张这样的卡片,他可以任选一张向你展示。当你提出提议时,你需要先问你右手边的玩家是否可以反驳你。如
果他没有反驳,你可以继续问这个人右手边的玩家,直到有人提出反驳的证据,或是所有人都无法反驳你的提议。许
多时候你可以从其他人的提议过程中获取信息。例如上面的例子,你是拥有卡片A和T的第三方玩家。如果有人向提
议者展示了反驳的证据,那么你可以知道那张卡片一定是武器L。在游戏过程中,保持对提议与反驳过程的追踪是很
重要的游戏策略。为了赢得游戏,你需要进行accusation(即指控),做出你对凶手、凶器和作案地点的最终猜测。在
你的指控开始后,你可以检查最开始被移除的三张卡片--如果它们与你的指控相符,你就赢得胜利啦!无需多说,你肯
定希望在提出指控前有绝对的把握。所以有了这道题。你是玩家1。给定你手上的卡片集合,以及一些提议与反驳的
记录,你需要确定你离能够做出指控还有多远。

输入格式

第一行包含一个整数n(1 ≤ n ≤ 50) ,表示游戏中已经完成的提议数量。
第二行包含你手上五张卡片的信息,它们是'A' 到'U'之间的大写字母。
接下来n行,每行给出一条提议的信息。
每行以三张卡片开始,依次表示提议的角色、武器和房间
接下来给出剩下三个玩家的响应,从提议者右边的玩家开始。
如果一个玩家没有证据反驳,则响应信息是一个'-' ,否则响应信息是一个证据字符。
如果证据对你是可见的 (你是提议者或反驳者) ,则证据字符是对应的卡片,否则证据字符是'*' 。
注意只有最后一条响应信息可以是证据字符。
所有字符之间用一个空格隔开。保证输入的提议和响应序列是合法的。

输出格式

输出三个字符表示能识别出的凶手、凶器和作案地点。
如果凶手可以被识别,输出相应的卡片字符,否则输出'?' 。凶器和作案地点同理。

样例

样例输入


			
样例1
1
B I P C F
A G M - - -
样例2
2
A B C D H
F G M M
F H M - *
样例3
3
A C M S D
B G S - G
A H S - - S
C J S *

样例输出


			
样例1
AGM
样例2
E??
样例3
???

数据范围与提示