Дистанционный практикум по программированию

Рассматриваются все разложения числа N в сумму натуральных слагаемых. Для сравнения разложения приводят к виду, когда слагаемые не возрастают слева направо. При сравнении идут по разложениям слева направо и находят первую пару чисел, различающихся в этих разложениях. На основании сравнения этих чисел делают заключение об отношении разложений.

 

Сравним разложения числа 40: 12+3+5+2+12+6 и 12+2+12+6+2+6.

Сначала приведём разложения к виду, когда слагаемые не возрастают слева направо: 12+12+6+5+3+2 и 12+12+6+6+2+2.

Затем начнём сравнивать числа разложений слева направо. Различие есть в четвёртом числе: в первом разложении это 5, во втором — 6. Число 5 меньше числа 6, поэтому первое разложение меньше второго.

 

Назовём разложение следующим за X, если оно больше X и не превосходит любого разложения, большего X.

 

Например, рассмотрим все различные с точки зрения задачи разложения числа 5:

1+1+1+1+1 < 2+1+1+1 < 2+2+1 < 3+1+1 < 3+2 < 4+1 < 5

Видно, что следующим за разложением 2+1+1+1 является разложение 2+2+1. А разложения, следующего за 5, не существует.

 

Дано разложение числа N <= 121. Требуется найти K-е (K <= 2 056 148 050) разложение того же числа, следующее за данным.

 

Замечание. Количество разложений числа 121 составляет 2 056 148 051.

 

В первой строке входного файла содержится исходное разложение, во второй — число K.

В выходной файл вывести требуемое разложение или "Impossible", если такого разложения не существует.

Примеры

STDIN	STDOUT
1+2+1+1 3	2+3
1+1+2+1 6	Impossible