题目描述

给定正整数 $N, L$ 和一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$。

对于 $i = 1, 2, \dots, N$，请回答以下问题：

是否存在一个长度为 $L$ 的非负整数序列 $B = (B_1, B_2, \dots, B_L)$，使得

$$\sum\_{j=1}^{L-1} \sum\_{k=j+1}^{L} |B\_j - B\_k| = A\_i$$

如果存在，请求出所有满足条件的 $B$ 中 $\max(B)$ 的最小值；如果不存在，请输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $L$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出 $N$ 行。第 $k$ 行对应 $i = k$ 时的答案。如果不存在满足条件的 $B$，输出 $-1$；如果存在，输出 $\max(B)$ 的最小值。

样例 1

输入

2 4
10 5

输出

3
-1

样例 2

输入

6 8
167 924 167167 167924 116677 154308

输出

11
58
10448
10496
7293
9645

说明/提示

约束条件

• $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$
• 输入均为整数

样例解释 1

对于 $A_1 = 10$，当 $B = (1, 0, 2, 3)$ 时，

$$\sum\_{j=1}^{L-1} \sum\_{k=j+1}^{L} |B\_j - B\_k| = 10$$

此时 $\max(B) = 3$。不存在 $\max(B) < 3$ 且满足条件的非负整数序列 $B$，所以第 $1$ 行应输出 $3$。

对于 $A_2 = 5$，不存在满足条件的非负整数序列 $B$，所以第 $2$ 行应输出 $-1$。

由 ChatGPT 4.1 翻译