安德烈收到了伊琳娜寄来的明信片。它只包含“你好,安德烈!”和一个由小写拉丁字母、雪花和拐杖糖组成的奇怪字符串。安德烈认为这个字符串是加密的消息,并决定解密它。
安德烈注意到雪花和拐杖糖总是站在字母后面,所以他认为该消息是按如下方式加密的。拐杖糖的意思是前面的字母可以去掉,或者可以留下。雪花意味着它前面的字母可以被删除、保留或重复多次。
例如,考虑以下字符串:
该字符串可以编码消息“happynewyear”。为此,应按以下方式使用拐杖糖和雪花:
- 拐杖糖1:删除字母w,
- 雪花 1:重复字母 p 两次,
- 拐杖糖2:留下字母n,
- 雪花2:删除字母w,
- 雪花3:留下字母e。
请注意,相同的字符串可以编码不同的消息。例如,上面的字符串可以编码“hayewyar”、“happpppynewwwwwyear”和其他消息。
Andrey 知道来自 Irina 的消息通常有 $$$k$$$ 个字母的长度。帮助他找出给定的字符串是否可以编码 $$$k$$$ 字母的消息,如果可以,请给出此类消息的示例。
输入
第一行包含明信片中收到的字符串。该字符串仅包含小写拉丁字母以及字符“*”和“?”,分别表示雪花和糖果锥。这些字符只能紧接在字母之后出现。字符串长度不超过$$$200$$$。
第二行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 200$$$),即所需的消息长度。
输出
打印给定字符串可以编码的长度为 $$$k$$$ 的任何消息,如果这样的消息不存在,则打印“不可能”。
示例
输入 #1
hw?ap*yn?eww*ye*ar 12
输出 #1
happynewyear
输入 #2
ab?a 2
输出 #2
aa
输入 #3
ab?a 3
输出 #3
aba
输入#4
ababb 5
输出#4
ababb
输入 #5
ab?a 1
输出 #5
Impossible