CF1099C Postcard
题目描述
Andrey 收到了一张来自 Irina 的明信片。明信片上只有“Hello, Andrey!”这句话，以及一个由小写拉丁字母、雪花符号和拐杖糖符号组成的奇怪字符串。Andrey 认为这个字符串是加密信息，并决定将其解密。
Andrey 注意到雪花和拐杖糖总是出现在字母后面，因此他猜测消息的加密方式如下：拐杖糖表示其前面的字母可以被删除，也可以保留。雪花表示其前面的字母可以被删除、保留，或者重复多次。
例如，考虑如下字符串：
这个字符串可以编码消息“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$ 的、该字符串可以编码出的消息。如果不存在这样的消息，则输出“Impossible”。
说明/提示
由 ChatGPT 4.1 翻译