Description

计算(a0 + a1x + a2x^2 + ... + an*x^n)^k的展开式。

Input

第一行一个整数T，代表共有T组数据 每组数据第一行有两个数n,k (0<n,k<=10) 每组数据第二行有n+1 个整数 a0,a1,...,an (-2<=ai<=2)

Output

对于每组数据，按x的幂从小到大输出其展开式。 1)系数为0的项不输出。 2)当x的指数为1时，省略指数 3)当系数为1或-1 ，且不为常数项时，省略系数 更多细节请参考样例。

Sample

Input

3
1 2
1 1
1 3
-1 -1
2 3
0 2 1

Output

1+2*x+x^2
-1-3*x-3*x^2-x^3
8*x^3+12*x^4+6*x^5+x^6

Hint

保证答案不会只有一个0，all the numbers will fit in 32-bit integers

Source: ziki