Shohag has an integer $$$n$$$ and a set $$$S$$$ of $$$m$$$ unique integers. Help him find the lexicographically largest$$$^{\text{∗}}$$$ integer array $$$a_1, a_2, \ldots, a_n$$$ such that $$$a_i \in S$$$ for each $$$1 \le i \le n$$$ and $$$a_{\operatorname{gcd}(i, j)} \neq \operatorname{gcd}(a_i, a_j)$$$$$$^{\text{†}}$$$ is satisfied over all pairs $$$1 \le i \lt j \le n$$$, or state that no such array exists.

$$$^{\text{∗}}$$$An array $$$a$$$ is lexicographically larger than an array $$$b$$$ of the same length if $$$a \ne b$$$, and in the first position where $$$a$$$ and $$$b$$$ differ, the array $$$a$$$ has a larger element than the corresponding element in $$$b$$$.

$$$^{\text{†}}$$$$$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le n \le 10^5$$$).

The second line contains $$$m$$$ unique integers in increasing order, representing the elements of the set $$$S$$$ ($$$1 \le x \le n$$$ for each $$$x \in S$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, if there is no solution print $$$-1$$$, otherwise print $$$n$$$ integers — the lexicographically largest integer array that satisfies the conditions.

Note

In the first test case, every element in the array belongs to the given set $$$S = \{3, 4, 6\}$$$, and all pairs of indices of the array satisfy the necessary conditions. In particular, for pair $$$(2, 3)$$$, $$$a_{\operatorname{gcd}(2, 3)} = a_1 = 6$$$ and $$$\operatorname{gcd}(a_2, a_3) = \operatorname{gcd}(4, 4) = 4$$$, so they are not equal. There are other arrays that satisfy the conditions as well but this one is the lexicographically largest among them.

In the third test case, there is no solution possible because we are only allowed to use $$$a = [2, 2]$$$ but for this array, for pair $$$(1, 2)$$$, $$$a_{\operatorname{gcd}(1, 2)} = a_1 = 2$$$ and $$$\operatorname{gcd}(a_1, a_2) = \operatorname{gcd}(2, 2) = 2$$$, so they are equal which is not allowed!

Shohag Loves GCD

Examples