Шопінг
Вчора Дені святкувала день народження і отримала багато подарунків від друзів. Тепер у неї є необмежена кількість усіх видів товарів, які продаються в магазинах торгового центру. Дені вирішила продати частину з них, щоб отримати певну суму грошей. З цими грошима вона планує піти за покупками в торговий центр разом з друзями, але купуватиме лише ті товари, які відрізняються від проданих. Після всього цього Дені хоче залишити собі певну суму грошей (якщо це можливо, просто продаючи частину подарунків, то вона не робитиме покупок). Оскільки існує багато видів товарів з різними цінами, їй потрібно вирішити, які товари продавати, а які купувати, щоб в результаті отримати бажану суму.
У магазинах є k видів товарів з цінами a[1], a[2], ..., a[k] левів (валюта Болгарії) відповідно, і Дені хоче в результаті мати рівно n левів. Вам потрібно визначити, скільки разів вона повинна купувати або продавати кожен тип товарів (купівля позначається від'ємним числом, а продаж - додатним), щоб у результаті у Дені було n левів. Ваша програма повинна обробити t тестів в одному наборі вхідних даних. Оскільки виведені числа можуть бути дуже великими, кожне число повинно бути виведене як добуток не більше ніж 100 цілих чисел. Якщо задача має більше одного розв'язку, ви можете вивести будь-який з них. Якщо розв'язку немає, виведіть текст "No solutions" (без лапок).
Вхідні дані
У першому рядку знаходиться одне додатне ціле число t (1 ≤ t ≤ 2) - кількість тестів, які ваша програма повинна обробити. Далі йде опис тестів. Для кожного тесту в першому рядку знаходиться число k (2 ≤ k ≤ 10^5), на наступному рядку - k натуральних чисел a[1], a[2], ..., a[k] (2 ≤ a[i] ≤ 10^9) - ціни для кожного типу товару в магазинах супермаркету. В останньому рядку опису тесту знаходиться натуральне число n (2 ≤ n ≤ 10^9) - кількість левів, яку Дені хоче мати в результаті.
Вихідні дані
Для кожного тесту необхідно вивести текст "No solutions" (без лапок), якщо задача не має розв'язку. Інакше потрібно вивести k чисел (кожне у форматі: num[1]num[2]...*num[p], 1 ≤ p ≤ 100, -10^9 ≤ num[1] ≤ 10^9, 0 ≤ num[i] ≤ 10^9 для 2 ≤ i ≤ p), які визначають, скільки разів товар кожного типу продається або купується Дені. Якщо число від'ємне, це означає, що вона купує цей товар, якщо додатне - вона його продає. Якщо це нуль, то це означає, що цей тип товару вона не купувала і не продавала. Якщо необхідно вивести, наприклад 1000000002, то воно може бути виведене у вигляді 2 * 500000001, але не 1000000002, тому що воно більше 10^9.