eolymp
bolt
Try our new interface for solving problems
Problems

Shopping

Shopping

Time limit 1 second
Memory limit 128 MiB

Deni's birthday was yesterday and she received a lot of gifts from many friends. It can be considered that due to the gifts she has an unlimited amount of all types of products that are also available in the stores of the Mall. Deni decides to sell some of them in order to get some money. Of course, with that money she will go shopping in the Mall with her friends, but she will buy only the types of products that are different from the sold ones. Deni wants to have a certain amount of money after all (if this can be done only with the selling of some of her presents, then she will postpone the shopping for another time). Since there are a lot of types of products with different prices, she has a hard time deciding which types of products she will sell and which she will buy; so that at the end she will have the decided in advance amount of money she wants.

Let there be k types of products in the stores, which have prices a[1], a[2], ..., a[k] levs (the Bulgarian currency) respectively and the girl wants to finish with exactly n levs. You have to output how many times she has to buy or sell every type of product (the buying is marked as a negative number and the selling – as a positive), so that at the end Deni to have n levs. Your program has to work for t tests in one example. Since the output numbers can be very large, each number has to be printed as a product of up to 100 whole numbers. If the task has more than one solution, you can print any one of them. If there is no solution, print the text "No solutions" (without quotes).

Input data

On the first line, there is one positive integer number t (1t2) - the number of tests that your program has to be processed. For each test on one line, there is k (2k10^5), and on the next line, there are k natural numbers - the prices of the types of products a[1], a[2], ..., a[k] (2a[i]10^9) in the Mall stores. On the last line for the test, there is the natural number n (2n10^9) - the money in levs that Deni wants to have at the end.

Output data

For each test there has to be the text "No solutions" (without quotes) if the task has no solutions, orotherwise: k whole numbers (each of them has to be in this form: num[1]num[2]...*num[p], 1p100, -10^9num[1]10[9], 0num[i]10^9 for 2ip), which describe how much times every type of product is bought or sold by Deni (if the number is negative then she buys this type of product and if it is positive - she sells it; if it is zero, then she neither buys it, nor sells it). If you have to output for example 1000000002, it can be printed, for example as 2 * 500000001, but not as 1000000002, because it is bigger than 10^9.

Examples

Input example #1
1
2
3 5
11
Output example #1
2 1
Input example #2
1
4
30 42 70 105
413
Output example #2
7 3*3 5 -1*5
Source 2017 IX International autumn tournament in informatics, Shumen, Junior, Day 2, Problem D