← 返回题目列表

AtCoder · pakencamp_2025_day1_m

M. 最小可整除数列

中文机器翻译题面 查看原题

配点 : 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 个测试用例没有良好的顺序。