CF1344D.Résumé Review

Uh oh! Applications to tech companies are due soon, and you've been procrastinating by doing contests instead! (Let's pretend for now that it is actually possible to get a job in these uncertain times.)

You have completed many programming projects. In fact, there are exactly $n$ types of programming projects, and you have completed $a_i$ projects of type $i$. Your résumé has limited space, but you want to carefully choose them in such a way that maximizes your chances of getting hired.

You want to include several projects of the same type to emphasize your expertise, but you also don't want to include so many that the low-quality projects start slipping in. Specifically, you determine the following quantity to be a good indicator of your chances of getting hired:

$$f(b\_1,\\ldots,b\_n)=\\sum\\limits\_{i=1}^n b\_i(a\_i-b\_i^2).$$

Here, $b_i$ denotes the number of projects of type $i$ you include in your résumé. Of course, you cannot include more projects than you have completed, so you require $0\le b_i \le a_i$ for all $i$.

Your résumé only has enough room for $k$ projects, and you will absolutely not be hired if your résumé has empty space, so you require $\sum\limits_{i=1}^n b_i=k$.

Find values for $b_1,\ldots, b_n$ that maximize the value of $f(b_1,\ldots,b_n)$ while satisfying the above two constraints.

糟糕！科技公司的申请截止日期快到了，而你却一直在拖延，转而参加编程竞赛！（我们暂且假设，在当前这种不确定的时期，实际上还是有可能找到工作的。）

你已完成许多编程项目。事实上，恰好有 $n$ 种类型的编程项目，而你已完成第 $i$ 类项目 $a_i$ 个。你的简历空间有限，但你希望精心挑选所要包含的项目，以最大化自己获得录用的机会。

你希望在简历中包含多个同类型项目，以突出自己在该领域的专长；但同时，你又不希望包含过多，以免质量较低的项目混入其中。具体而言，你确定以下量可作为获聘概率的一个良好指标：

$$f(b_1,\ldots,b_n)=\sum\limits_{i=1}^n b_i(a_i-b_i^2).$$

其中，$b_i$ 表示你在简历中包含的第 $i$ 类项目的数量。当然，你无法包含超过自己实际完成数量的项目，因此对所有 $i$ 都要求满足 $0\le b_i \le a_i$。

你的简历仅能容纳 $k$ 个项目；而且，若简历未填满，则你将绝对无法获得录用，因此还必须满足 $\sum\limits_{i=1}^n b_i=k$。

请找出满足上述两个约束条件、并使 $f(b_1,\ldots,b_n)$ 取得最大值的 $b_1,\ldots, b_n$ 的取值。

The first line contains two integers $n$ and $k$ ($1\le n\le 10^5$, $1\le k\le \sum\limits_{i=1}^n a_i$) — the number of types of programming projects and the résumé size, respectively.

The next line contains $n$ integers $a_1,\ldots,a_n$ ($1\le a_i\le 10^9$) — $a_i$ is equal to the number of completed projects of type $i$.

第一行包含两个整数 $n$ 和 $k$（$1\le n\le 10^5$，$1\le k\le \sum\limits_{i=1}^n a_i$），分别表示编程项目类型的数量和简历的大小。

接下来一行包含 $n$ 个整数 $a_1,\ldots,a_n$（$1\le a_i\le 10^9$），其中 $a_i$ 表示第 $i$ 类已完成的项目数量。

In a single line, output $n$ integers $b_1,\ldots, b_n$ that achieve the maximum value of $f(b_1,\ldots,b_n)$, while satisfying the requirements $0\le b_i\le a_i$ and $\sum\limits_{i=1}^n b_i=k$. If there are multiple solutions, output any.

Note that you do not have to output the value $f(b_1,\ldots,b_n)$.

在一行中输出 $n$ 个整数 $b_1,\ldots, b_n$，使其在满足约束条件 $0\le b_i\le a_i$ 且 $\sum\limits_{i=1}^n b_i=k$ 的前提下，使 $f(b_1,\ldots,b_n)$ 取得最大值。若存在多个解，输出任意一个即可。

注意：你无需输出 $f(b_1,\ldots,b_n)$ 的值。

For the first test, the optimal answer is $f=-269$. Note that a larger $f$ value is possible if we ignored the constraint $\sum\limits_{i=1}^n b_i=k$.

For the second test, the optimal answer is $f=9$.

对于第一个测试用例，最优解为 $f=-269$。注意，若忽略约束条件 $\sum\limits_{i=1}^n b_i=k$，则可得到更大的 $f$ 值。

对于第二个测试用例，最优解为 $f=9$。