Sum of Abs 2

时间限制：2s
空间限制：512MB

题目描述

给定正整数 $N,L$ 和长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。对每个 $i=1,2,\ldots,N$，判定是否存在长度为 $L$ 的非负整数序列 $B=(B_1,B_2,\ldots,B_L)$，使得

如果存在，求所有满足条件的 $B$ 中 $\max(B)$ 的最小值。

输入格式

第一行包含两个整数 $N,L$。第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出 $N$ 行。第 $i$ 行中，若不存在满足条件的 $B$，输出 $-1$；否则输出最小的 $\max(B)$。

样例输入 1

2 4
10 5

样例输出 1

3
-1

样例输入 2

6 8
167 924 167167 167924 116677 154308

样例输出 2

11
58
10448
10496
7293
9645

数据范围

• $1\le N\le 2\times 10^5$。
• $2\le L\le 2\times 10^5$。
• $1\le A_i\le 2\times 10^5$。