某款冒险游戏维护了一个指令库,其中包含 n 条互不相同的完整指令。
玩家会依次输入 m 条字符串作为输入指令。输入指令可以是完整指令本身,也可以是某条完整指令的前缀(从第 1 个字符开始连续匹配)。
对于每条输入指令 s,定义它与指令库的匹配结果如下:
• 若存在且仅存在一条完整指令 c 满足:s 是 c 的前缀,则认为 s 唯一匹配到 c,系统执行该指令,并输出 c。
• 若有两条或以上的完整指令都以 s 作为前缀,则认为 s 多重匹配,输出ambiguous。
• 若指令库中不存在任何以 s 为前缀的完整指令,则认为 s 无法匹配,输出unknown。
现在,请你对玩家输入的每条指令,按上述规则输出其匹配结果。
第一行包含两个整数 n, m,分别表示指令库中的完整指令数量,以及玩家输入指令的数量。
接下来 n 行,每行一个字符串,表示一条完整指令。
接下来 m 行,每行一个字符串,表示一条输入指令。
输出 m 行。第 i 行对应第 i 条输入指令的匹配结果:
• 唯一匹配:输出对应的完整指令;
• 多重匹配:输出 ambiguous;
• 无法匹配:输出 unknown。
6 5 attack defend move magic examine exit att def mov ex e
attack defend move ambiguous ambiguous
【样例说明 1】
指令库为:attack、defend、move、magic、examine、exit。
• att 是 attack 的前缀,且仅匹配这一条,输出 attack。
• def 仅匹配 defend,输出 defend。
• mov 仅匹配 move,输出 move。
• ex 同时匹配 examine 与 exit,属于多重匹配,输出 ambiguous。
• e 同时匹配 examine 与 exit,输出 ambiguous。
【样例输入 2】
4 4
open
close
operate
unlock
op
clo
un
cast
【样例输出 2】
ambiguous
close
unlock
unknown
【样例说明 2】
• op 同时匹配 open 与 operate,输出 ambiguous。
• clo 仅匹配 close,输出 close。
• un 仅匹配 unlock,输出 unlock。
• cast 无法匹配任何完整指令,输出 unknown。
【评测用例规模与约定】
对于 30% 的评测用例,n ≤ 10,m ≤ 10;
对于 60% 的评测用例,n ≤ 50,m ≤ 50;
对于所有评测用例,1 ≤ n ≤ 100,1 ≤ m ≤ 100;
保证所有指令名称和输入指令的长度均在 [1, 20] 之间,所有字符串仅包含小写英文字母,指令库中的完整指令互不相同。