题目描述

一家软件公司有 $k$ 名程序员。他们需要参与 $n$ 个项目，第 $i$ 个项目的难度为 $x_i$。

每名程序员最多只能参与 一个 项目，因此公司希望安排每个项目分配到的程序员数量为 $y_i$，其中对每个 $i$ 都有 $y_i$ 为非负整数，并满足：

不过，程序员们的合作效率遵循“人多未必力量大”的规律，因此在项目 $i$ 上，若分配了 $y_i$ 名程序员，则该项目产生的生产力仅为：

公司希望对程序员进行分配，使得所有项目的总生产力最大。

输入格式

第一行包含两个数 $n,k$。

第二行包含 $n$ 个数 $x_1,x_2,\ldots,x_n$，表示各项目难度。

输出格式

输出一行 $n$ 个整数 $y_1,y_2,\ldots,y_n$，表示一种使总生产力最大的分配方案。

如果你的方案得到的总生产力与标准答案的差值不超过 $10^{-10}$，则该答案会被判为正确。

数据范围

• $1 \le n \le 10^6$
• $1 \le k \le 10^{12}$
• $1 \le x_i \le 10^6$
• $x_i$ 为一个小数，且小数点后最多有 $6$ 位

子任务

只有当某个子任务的全部测试点均通过时，才能获得该子任务的分数。

样例

输入

3 3
1.2 2.5 3.7

输出

2 1 0