题目描述

某中学的 $n$ 个班正在上课，第 $i$ 个班有 $a_i$ 名学生。

突然，放学铃声炸响！眨眼间，已经有 $k$ 名学生冲出了校门。但有一个班却纹丝不动——因为他们的老师还在拖堂，这个班的学生一个都没能跑掉。

你站在走廊上，看着这混乱的场面，突然冒出一个数学问题：假设拖堂的是第 $j$ 个班，那么在剩下的 $n−1$ 个班里，剩余人数最多的那个班，最少会剩下多少人？注意，逃跑的 $k$ 名学生只能来自非拖堂的班级，且每个班跑掉的人数不能超过他们原来的人数。

请你对于每一个可能的拖堂班级 $j$（从 $1$ 到 $n$），计算出这个“最少的最大班级人数”。

输入格式

第一行两个正整数 $n$，$k$，含义如上所述。

第二行 $n$ 个正整数 $a_i$，含义如上所述。

建议使用较快的读入方式。

输出格式

一行 $m$ 个整数，第 $i$ 个整数表示恰好只有班级 $i$ 的老师还在拖堂，在剩下的未拖堂的班级中，还留在学校的人数最多的班级的最少的可能人数是多少。如果班级 $i$ 拖堂就不可能有 $k$ 名学生冲出学校，则输出 $-1$。

3 3
1 2 3

1 1 0

3 4
1 2 3

1 0 -1

数据规模与约定

下发文件

下发文件满足子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^6, 1 \leq k \leq \sum a_i,1 \leq a_i \leq 10^{12}$。