在军队中,要组建一支能在战场上发挥作用的士兵队伍并不容易。沟通至关重要,因此任何两个士兵都不应该共用一个名字(如果他们收到鲍勃是侦察员的命令,如果有两个鲍勃,会发生什么?)。
一组士兵有效当且仅当他们的名字不同时。例如,组(John、Bob、Limak)会有效,而组(Gary、Bob、Gary)和(Alice、Alice)则不会。
你是敌方阵营的间谍。你注意到 n 个士兵站成一排,编号为 1 到 n。将军想要选择一组连续的 k 个士兵。对于每 k 个连续的士兵,将军写下他们是否是一个有效的团队。
你成功窃取了将军的笔记,其中包含 n - k + 1 个字符串 s1、s2、...、sn - k + 1,每个字符串要么是“是”,要么是“否”。
- 字符串 s1 描述一组士兵 1 到 k(如果该组有效,则为“YES”,否则为“NO”)。
- 字符串 s2 描述一组士兵 2 到 k + 1。
- 依此类推,直到字符串 sn - k + 1 描述一组士兵 n - k + 1 到 n。
你的任务是找到 n 个士兵的可能名字。姓名应与被盗笔记相符。每个名称应该是由 1 到 10 个英文字母组成的字符串(含 1 到 10 个英文字母)。第一个字母应为大写,所有其他字母应为小写。名称不必是现有名称 - 例如,可以打印“Xyzzzdj”或“T”。
查找并打印任何解决方案。可以证明,总是存在至少一个解。
输入
输入的第一行包含两个整数 n 和 k (2 ≤ k ≤ n ≤ 50)——分别是士兵的数量和团体的规模。
第二行包含n - k + 1个字符串s1,s2,...,sn - k + 1。如果第i到i + k - 1组士兵有效,则字符串si为“YES”,否则为“NO”。
输出
找到满足所有给定条件的任何解决方案。在一行中打印 n 个空格分隔的字符串,表示顺序中士兵的可能名称。每个名称的第一个字母应大写,其他字母应小写。每个名称只能包含英文字母,长度为 1 到 10。
如果有多个有效的解决方案,则打印其中任何一个。
示例
输入 #1
8 3 NO NO YES YES YES NO
输出 #1
Adam Bob Bob Cpqepqwer Limak Adam Bob Adam
输入 #2
9 8 YES NO
输出 #2
R Q Ccccccccc Ccocc Ccc So Strong Samples Ccc
输入 #3
3 2 NO NO
输出 #3
Na Na Na
注意
在第一个样本中,有 8 名士兵。每连续 3 个,我们就知道他们是否是一个有效的群体。让我们分析一下提供的示例输出:
- 前三名士兵(即 Adam、Bob、Bob)不会是一个有效的团队,因为有两个 Bob。事实上,字符串 s1 是“NO”。
- 士兵 2 到 4(Bob、Bob、Cpqepqwer)也不会有效,并且字符串 s2 为“NO”。
- 士兵 3 到 5(Bob、Cpqepqwer、Limak)将有效,并且字符串 s3 为“YES”。
- ...,
- 士兵 6 到 8(Adam、Bob、Adam)不会有效,字符串 s6 为“NO”。