Зверніть увагу, що тут Вас просять відновити детальну відповідь (сукупність банкнот), ще й в умовах відносно невеликого обсягу дозволеної пам'яті.

У деякій державі в обігу перебувають банкноти певних номіналів. Національний банк хоче, щоб банкомат видавав будь-яку запитану суму за допомогою мінімального числа банкнот, вважаючи, що запас банкнот кожного номіналу необмежений. Допоможіть Національному банку вирішити цю задачу.

Вхідні дані

Перший рядок містить натуральне число ~N~ – кількість номіналів банкнот у обігу. Другий рядок вхідних даних містить ~N~ різних натуральних чисел ~x_1~, ~x_2~, ..., ~x_N~ – номінали банкнот. Третій рядок містить натуральне число ~S~ – суму, яку необхідно видати.

Обмеження та особливості оцінювання

Як завжди, мається на увазі, що можна отримати бали лише за деякі (один) з блоків, можна за всі (обидва), але для отримання балів за блок треба, щоб програма успішно пройшла всі тести блоку.

Перевірено, що якщо взяти правильний алгоритм і акуратно його реалізувати, то програма вкладається в обмеження мовами C#, C++, Java. Реалізувати те саме мовою Python (так, щоб проходив блок 2) поки що вдалося лише дещо дивним чином: треба здавати «мовою» PyPy3, а не Python3; в цій задачі «мові» PyPy3 був виставлений вищий, чим стандартний, Memory Limit, чесність чого дуже-дуже дискусійна.

Результати

Програма повинна знайти подання числа ~S~ у вигляді суми доданків з множини ~x_i~, що містить мінімальне число доданків, і вивести це подання у вигляді послідовності чисел, розділених пробілами.

Якщо таких подань існує декілька, то програма повинна вивести будь-яке (одне) з них. Якщо такого подання не існує, то програма повинна вивести рядок No solution.

Приклади

Вхід

7
1 2 5 10 20 50 100
72

Результат

50 20 2

Вхід

2
20 50
60

Результат

20 20 20