learned Dirichlet convolution during the previous camp. However, compared with deep reinforcement learning, it's too easy for him. Therefore, he did something special.
If are two functions from the positive integers to the integers, the Dirichlet convolution is a new function defined by: (f * g)(n) =\sum_{d \mid n}f(d)g ({\frac {n}{d}}) .
We define the -th power of an function by f^{k}=\underbrace {f * \dots * f} _{k~{\textrm {times}}}.
In this problem, we want to solve the inverse problem: Given and , you need to find a function such that .
Moreover, there is an additional constraint that and must equal to . And all the arithmetic operations are done on where , which means that in the Dirichlet convolution, .
输入格式
The first line contains two integers and .
The second line contains n integers ().
输出格式
If there is no solution, output .
Otherwise, output (). If there are multiple solutions, print anyone.
