← 返回题目列表

Codeforces · 1099/C

C. 明信片

中文机器翻译题面 查看原题

安德烈收到了伊琳娜寄来的明信片。它只包含“你好,安德烈!”和一个由小写拉丁字母、雪花和拐杖糖组成的奇怪字符串。安德烈认为这个字符串是加密的消息,并决定解密它。

安德烈注意到雪花和拐杖糖总是站在字母后面,所以他认为该消息是按如下方式加密的。拐杖糖的意思是前面的字母可以去掉,或者可以留下。雪花意味着它前面的字母可以被删除、保留或重复多次。

例如,考虑以下字符串:

该字符串可以编码消息“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