Андрей получил открытку от Ирины. В ней были только слова «Привет, Андрей!» и странная строка, состоящая из строчных латинских букв, снежинок и леденцов. Андрей подумал, что эта строка — это зашифрованное сообщение, и решил его разгадать.
Андрей заметил, что снежинки и леденцы всегда стоят после букв, поэтому у него появилась гипотеза, что сообщение закодировано следующим образом. Леденец означает, что символ, идущий перед ним, можно удалить, а можно оставить. Снежинка же означает, что символ, идущий перед ней, можно удалить, оставить или повторить несколько раз.
Например, рассмотрим такую строку:
Эта строка может кодировать сообщение «happynewyear». Для этого леденцы и снежинки нужно использовать следующим образом:
- леденец 1: удалить букву w,
- снежинка 1: повторить символ p два раза,
- леденец 2: оставить букву n,
- снежинка 2: удалить букву w,
- снежинка 3: оставить букву e.
Обратите внимание, что одна и та же строка может кодировать разные сообщения. Например, строка, приведенная выше, может кодировать сообщения «hayewyar», «happpppynewwwwwyear» и другие.
Андрей знает, что сообщения от Ирины обычно имеют длину \(k\) символов. Помогите ему понять, может ли данная строка кодировать какое-то сообщение из \(k\) символов, и если да, приведите пример такого сообщения.
Выходные данные
Выведите любое сообщение длины \(k\), которое может кодировать данная строка, или «Impossible», если такого сообщения не существует.