解题思路

先把题意抽象一下：

一次操作本质上是：

• 选一个偶数 $a_i$
• 从 $a_i$ 身上拿走一个因子 $2$，即 $a_i \leftarrow a_i / 2$
• 再把这个因子 $2$ 送给某个 $a_j$，即 $a_j \leftarrow a_j \times 2$

题目内容

小红拿到了一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$。她可以进行最多 $k$ 次如下操作：

• 步骤一：选择两个下标的元素 $a_i$ 和 $a_j$（即满足 $i \neq j$），且 $a_i$ 为偶数；
• 步骤二：将 $a_i$ 除以 $2$，同时将 $a_j$ 乘以 $2$。

经过最多 $k$ 次操作后，小红希望数组的字典序尽可能小。由于操作后数组元素可能非常大，良心的小红不需要你写高精度进行计算，只需要你输出操作结束后数组中每个元素末尾有多少个 $0$（十进制表示下的尾随零）即可。

从数组的第一个元素开始逐个比较，直到找到第一个不同的位置，比较这个位置元素的大小，较小的数组的字典序也较小。

输入描述

在一行上输入两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 10^9$），分别表示数组长度和最多操作次数；

在第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^9$），表示数组的初始元素。

输出描述

在一行上输出 $n$ 个整数，第 $i$ 个整数表示操作结束后第 $i$ 个元素末尾 $0$ 的数量。

样例1

输入

5 1
1 2 3 4 5

输出

0 0 0 0 1

说明

在上述样例中，初始数组为 $\{1,2,3,4,5\}$。

• 小红进行一次操作，选择 $a_i = 2$ 和 $a_j = 5$；
• 将 $2$ 除以 $2$ 得到 $1$，将 $5$ 乘以 $2$ 得到 $10$；

最终数组为 $\{1,1,3,4,10\}$，各元素末尾 $0$ 的个数依次为 $\{0,0,0,0,1\}$。

样例2

输入

3 20
1024 5 125

输出

0 0 3