Score : $600$ points

问题陈述

给定正整数 $N$ 和 $L$，以及长度为 $N$ 的正整数序列 $A = (A_{1}, A_{2}, \dots , A_{N})$。

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

确定是否存在一个非负整数序列 $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}$。如果存在，找到这样的序列 $B$ 的 $\max(B)$ 的最小值。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given positive integers $N$ and $L$, and a sequence of positive integers $A = (A_{1}, A_{2}, \dots , A_{N})$ of length $N$.

For each $i = 1, 2, \dots , N$, answer the following question:

Determine if there exists a sequence of $L$ non-negative integers $B = (B_{1}, B_{2}, \dots, B_{L})$ such that $\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = A_{i}$. If it exists, find the minimum value of $\max(B)$ for such a sequence $B$.

Constraints

• $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}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $L$

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

Output

Print $N$ lines. The $k$-th line should contain -1 if no sequence $B$ satisfies the condition for $i=k$; otherwise, it should contain the minimum value of $\max(B)$ for such a sequence $B$.

Sample Input 1

2 4
10 5

Sample Output 1

3
-1

For $A_{1} = 10$, if we take $B = (1, 0, 2, 3)$, then $\displaystyle \sum_{j = 1} ^ {L - 1} \sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = 10$, where $\max(B) = 3$. No non-negative integer sequence $B$ satisfies the condition with $\max(B) < 3$, so print $3$ in the first line.

For $A_{2} = 5$, there is no non-negative integer sequence $B$ that satisfies the condition, so print -1 in the second line.

Sample Input 2

6 8
167 924 167167 167924 116677 154308

Sample Output 2

11
58
10448
10496
7293
9645