配点 : 500 点
問題文
长度 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 以下
- 所有输入均为整数 仅当
入力
输入将以以下形式从标准输入给出。
T
\text{testcase}_1
\text{testcase}_2
\vdots
\text{testcase}_T
每个测试用例均按以下格式给出。
N K A_1 A_2 \ldots A_N
出力
对于每个测试用例,如果不存在好的序列 -1 。
如果有,则选择字典顺序最小的一个。 按以下格式输出为 B'=(B'_1,B'_2,\ldots,B'_N) 。 对于第
B'_1 B'_2 \ldots B'_N
入力例 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 个测试用例没有良好的顺序。