题目内容

小蓝有 $n$ 瓶魔法药剂排成一列，第 $i$ 瓶的魔力值为 $a_i$。每瓶药剂的魔力值由其包含的两种神秘成分决定：时光之尘和空间之尘。具体而言，$a_i$ 可以唯一表示为 $a_i = 2^{u_i} \times 5^{v_i} \times w_i$，其中 $w_i$ 与 $2$ 和 $5$ 互质。我们称 $u_i$ 为药剂 $i$ 的时光值，$v_i$ 为空间值，$w_i$ 为惰性基底。

小蓝可以施展最多 $k$ 次「时光转移」操作：每次选择两个不同的药剂 $i$ 和 $j$，且要求 $u_i \ge 1$，然后将药剂 $i$ 的 $1$ 单位时光值转移到药剂 $j$（即 $u_i$ 减少 $1$，$u_j$ 增加 $1$）。空间值和惰性基底始终保持不变。

她希望经过操作后，这一列药剂的魔力值序列的字典序尽可能小。字典序的比较规则为：从第一瓶到第 $n$ 瓶依次比较魔力值，一旦遇到不相等的魔力值，魔力值较小的序列被认为字典序更小。由于惰性基底固定且均为正数，魔力值的大小仅由时光值决定：时光值越小，魔力值越小。因此为了字典序最小，应尽可能优先减小前面药剂的时光值，并将减下的时光转移到后方。将时光全部集中到最后一瓶是一种最优的选择。

小蓝并不关心最终的魔力值具体是多少，她只想知道在最优操作下，每瓶药剂的「稳定度」。一瓶药剂的稳定度定义为 $\min(u_i, v_i)$，这也恰好等于该药剂魔力值在十进制表示下末尾连续零的个数。请你计算出每瓶药剂的最终稳定度。

药剂数量 $n$ 不超过 $10^5$，最多操作次数 $k$ 不超过 $10^9$，所有初始魔力值 $a_i$ 均为不超过 $10^9$ 的正整数。

输入描述

第一行包含两个整数 $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$ 瓶药剂的稳定度，相邻整数之间用一个空格分隔。

样例1

输入

3 2
8 2 4

输出

0 0 0

说明

首先计算每瓶药剂的时光值 $u_i$（因子 $2$ 的个数）和空间值 $v_i$（因子 $5$ 的个数）。

• 药剂 1：8 $=2^3$，$u_1=3$，$v_1=0$；
• 药剂 2：2 $=2^1$，$u_2=1$，$v_2=0$；
• 药剂 3：4 $=2^2$，$u_3=2$，$v_3=0$。

为了字典序最小，应优先减小前面药剂的时光值。当前 $k=2$。药剂 1 最多可转移 $\min(3,2)=2$ 单位时光至最后一瓶药剂。转移后 $u_1$ 变为 $1$，$u_3$ 变为 $4$，剩余 $k=0$。最终 $u=[1,1,4]$，$v=[0,0,0]$。稳定度 $\min(u_i,v_i)$ 分别为 $0,0,0$。

样例2

输入

3 0
8 10 5

输出

0 1 0

说明

$k=0$，无法进行任何操作，时光值保持不变。

• 8 $=2^3$，$u_1=3$，$v_1=0$；
• 10 $=2 \times 5$，$u_2=1$，$v_2=1$；
• 5 $=5^1$，$u_3=0$，$v_3=1$。

稳定度直接由初始的 $\min(u_i,v_i)$ 给出：药剂 1 $\min(3,0)=0$；药剂 2 $\min(1,1)=1$；药剂 3 $\min(0,1)=0$。因此输出 0 1 0。

样例3

输入

1 5
20

输出

1

说明

只有一瓶药剂，无论 $k$ 为多少都无法进行转移操作（需要两个不同的药剂）。 20 $=2^2 \times 5^1$，$u_1=2$，$v_1=1$。稳定度 $\min(2,1)=1$，恰好也是 20 十进制末尾连续零的个数。输出 1。

样例4

输入

4 10
8 2 10 10

输出

0 0 0 1

说明

计算初始 $u$、$v$：

• 8 $=2^3$，$u_1=3,v_1=0$；
• 2 $=2^1$，$u_2=1,v_2=0$；
• 10 $=2 \times 5$，$u_3=1,v_3=1$；
• 10 $=2 \times 5$，$u_4=1,v_4=1$。

$k=10$ 足够将所有前面的时光值转移至最后一瓶。依次转移： 药剂 1 转 $3$ 单位时光到药剂 4，$u=[0,1,1,4],k=7$； 药剂 2 转 $1$ 单位，$u=[0,0,1,5],k=6$； 药剂 3 转 $1$ 单位，$u=[0,0,0,6],k=5$。

最终 $u=[0,0,0,6]$，$v=[0,0,1,1]$。稳定度依次为 $\min(0,0)=0$，$\min(0,0)=0$，$\min(0,1)=0$，$\min(6,1)=1$。故输出 0 0 0 1。