← 返回题目列表

AtCoder · arc178_c

C. Abs 2 之和

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

分数: 600 点

问题陈述

给你正整数 N 和 L,以及正整数序列 A = (A_{1}, A_{2}, \dots , A_{N}) 长度 N.

对于每个 i = 1, 2, \dots , N,回答以下问题:

判断是否存在序列 L 非负整数 B = (B_{1}, B_{2}, \dots, B_{L}) 这样 \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}。如果存在,求最小值 \max(B) 对于这样的序列 B.

约束

  • 1 \leq N \leq 2 \times 10^{5}
  • 2 \leq L \leq 2 \times 10^{5}
  • 1 \leq A_{i} \leq 2 \times 10^{5}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N L
A_{1} A_{2} \cdots A_{N}

输出

打印 N 行。的 k- 第行应包含 -1 如果没有序列 B 满足条件 i=k;否则,它应该包含最小值 \max(B) 对于这样的序列 B.


示例输入 1

2 4
10 5

示例输出 1

3
-1

对于 A_{1} = 10, 如果我们采取 B = (1, 0, 2, 3),那么 \displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10,其中 \max(B) = 3。 没有非负整数序列 B 满足条件 \max(B) < 3,所以打印 3 在第一行。

对于 A_{2} = 5, 不存在非负整数序列 B 满足条件,所以打印 -1 在第二行。


示例输入 2

6 8
167 924 167167 167924 116677 154308

示例输出 2

11
58
10448
10496
7293
9645