問題文

長さ N の正整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

以下を満たす長さ N の正整数列 B=(B_1,B_2,\ldots,B_N) を 良い数列 と呼びます。

• |B_i-B_{i+1}|\le 1(1\le i<N)
• B_i は A_i の約数 (1\le i\le N)
• B_i=B_{i+1} となる i(1\le i<N) は丁度 K 個

良い数列が存在するか判定し、存在するならばそのうち辞書順最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 1\le T,N
• 0\le K<N
• 1\le A_i\le 10^{18}
• 全てのテストケースに対する N の総和は 2\times 10^5 以下
• 入力は全て整数

入力例 1

3
4 1
3 4 2 5
4 0
3 4 2 5
1 0
1

出力例 1

1 1 2 1
-1
1

1 番目のテストケースについて、辞書順最小の良い数列は (1,1,2,1) です。

2 番目のテストケースについて、良い数列は存在しません。