Postcard

题意翻译

## Description 给定一个长度为 $n$ 的字符串，尽可能包含小写字母，字符 '?' 和字符 ‘*’。保证上面两种特殊字符若出现则一定出现在一个小写字母的后面一位。要求构造一个长度为 $k$ 的新字符串，它和原串有如下关系： > 按照原串的字母顺序向新串中填充，新串中含且仅含小写字母。 > > 若原串的某小写字母后没有特殊字符，则这个字母在新串中必须保留 > > 若原串的某小写字母后有字符 '?'，则这个字母在新串中可以被保留，也可以被删除 > > 若原串某小写字母后有字符 '*'，则这个字母在新串中可以被保留，可以被删除，也可以被复读很多遍。 ## Input 第一行是一个长度为 $n$ 的字符串，保证输入合法 第二行是一个整数 $k$ 代表要求构造的新串长度 ## Output 输出一行一个长度为 $k$ 的字符串，为构造出的串。 若不存在这样的串，输出“Impossible”（不含引号） ## Hint $1~\leq~n,k~\leq~200$ translated by @一扶苏一

题目描述

Andrey received a postcard from Irina. It contained only the words "Hello, Andrey!", and a strange string consisting of lowercase Latin letters, snowflakes and candy canes. Andrey thought that this string is an encrypted message, and decided to decrypt it. Andrey noticed that snowflakes and candy canes always stand after the letters, so he supposed that the message was encrypted as follows. Candy cane means that the letter before it can be removed, or can be left. A snowflake means that the letter before it can be removed, left, or repeated several times. For example, consider the following string: This string can encode the message «happynewyear». For this, candy canes and snowflakes should be used as follows: - candy cane 1: remove the letter w, - snowflake 1: repeat the letter p twice, - candy cane 2: leave the letter n, - snowflake 2: remove the letter w, - snowflake 3: leave the letter e. Please note that the same string can encode different messages. For example, the string above can encode «hayewyar», «happpppynewwwwwyear», and other messages. Andrey knows that messages from Irina usually have a length of $ k $ letters. Help him to find out if a given string can encode a message of $ k $ letters, and if so, give an example of such a message.

输入输出格式

输入格式

The first line contains the string received in the postcard. The string consists only of lowercase Latin letters, as well as the characters «\*» and «?», meaning snowflake and candy cone, respectively. These characters can only appear immediately after the letter. The length of the string does not exceed $ 200 $ . The second line contains an integer number $ k $ ( $ 1 \leq k \leq 200 $ ), the required message length.

输出格式

Print any message of length $ k $ that the given string can encode, or «Impossible» if such a message does not exist.

输入输出样例

输入样例 #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