刺猬和他的朋友最喜欢的娱乐活动之一就是取一些句子或一首歌,并用彼此的名字替换一半的单词(有时甚至全部)。
朋友的生日快到了,刺猬决定给他的朋友做一份特别的礼物:一首很长的歌,其中他的名字会重复很多次。但无论他如何努力,他都写不出一首像样的歌!
问题是,刺猬已经决定了最终的句子应该有多长(即它应该包含多少个字母)以及朋友的名字应该出现在句子中的哪个位置,并且它不能出现在句子中的任何其他位置。此外,刺猬决定限制自己在这句话中只使用英文字母表的前 K 个字母(所以它甚至不是一个句子,而是一个长单词)。
由此产生的问题确实相当复杂,这就是为什么刺猬要求你帮助他编写一个程序,根据给定的名称 P、所需单词的长度 N、名称 P 在所需单词中出现的给定位置以及字母表的大小 K 来生成所需的单词。请注意,名称的出现可以相互重叠。
输入
第一行包含数字 N 和 K,它们是所需字符串的长度和相应的字母大小。限制为:1 ≤ N ≤ 100、2 ≤ K ≤ 26。
第二行包含名称 P,它是一个非空字符串,长度不超过 N 个字符。该字符串仅包含英文字母表的前 K 个小写符号。
第三行包含长度为 N - length(P) + 1 的字符串,仅包含数字 0 和 1。第 i 个位置上的数字 1 表示名称 P 的出现应该从所需单词的第 i 个位置开始,而零表示从这里开始没有出现。
输出
打印所需的单词 S。如果有多个答案,则打印其中任何一个。
如果无解,则打印“无解”。
示例
输入 #1
5 2 aba 101
输出 #1
ababa
输入 #2
5 2 a 10001
输出 #2
abbba
输入 #3
6 2 abba 101
输出 #3
No solution