Вчера был день рожденья Дени, и она получила много подарков от своих друзей. Можно сказать, что благодаря этим подаркам у нее теперь есть неограниченное количество всех типов товаров, которые продаются в магазинах торгового центра. Дени решила продать какие-то из них, чтобы получить некоторое количество денег. Конечно, с этими деньгами она отправится за покупками в торговый центр со своими друзьями, но она будет покупать только те типы товаров, которые отличаются от тех, которые она продала. После всего этого Дени хочет остаться с определенным количество денег (если это возможно сделать только путем продажи некоторых из ее подарков, то она не будет делать покупки). Так как имеется множество типов товаров с различными ценами, то ей предстоит трудный выбор – какие товары продавать, а какие покупать, чтобы в конце концов получить то количество денег, которые она хочет.

Пусть в магазинах имеется k типов товаров с ценами a1, a2, ..., ak левов (валюта Болгарии) соответственно, и Дени хочет в итоге иметь ровно n левов. Вы должны вывести сколько раз она должна покупать или продавать каждый тип товаров (покупка обозначается отрицательным числом, а продажа - положительным), чтобы в итоге у Дени было n левов. Ваша программа должна обработать t тестов в одном наборе входных данных. Так как выводимые числа могут быть очень большими, каждое число должно быть выведено как произведение не более чем 100 целых чисел. Если задача имеет более одного решения, вы можете вывести любое из них. Если решения нет, выведите текст "**No solutions**" (без кавычек).

Входные данные

В первой строке находится одно положительное целое число t (1 ≤ t ≤ 2) - количество тестов, которые Ваша программа должна обработать. Далее идет описание тестов. Для каждого теста в первой строке находится число k (2 ≤ k ≤ 105), на следующей строке - k натуральных чисел a1, a2, ..., ak (2 ≤ ai ≤ 109) - цены для каждого типа товара в магазинах супермаркета. В последней строке описания теста находится натуральное число n (2 ≤ n ≤ 109) - количество левов, которое Дени хочет иметь в итоге.

Выходные данные

Для каждого теста необходимо вывести текст "**No solutions**" (без кавычек), если задача не имеет решения. Иначе нужно вывести k чисел (каждое в формате: num1num2...*nump, 1 ≤ p ≤ 100, -109 ≤ num1 ≤ 109, 0 ≤ numi ≤ 109 для 2 ≤ i ≤ p), которые определяют, сколько раз товар каждого типа продается или покупается Дени. Если число отрицательное, это означает, что она покупает этот товар, если положительное - она его продает. Если это ноль, то это означает, что этот тип товара она не покупала и не продавала. Если необходимо вывести, например 1000000002, то оно может быть выведено в виде 2 * 500000001, но не 1000000002, потому что оно больше 109.