星环铸字工坊

题目描述

在星环城，每个区块的门牌由能量字符晶体组成。每个大写字母对应一种晶体。

有 $n$ 个区块，第 $i$ 个区块的门牌字符串为 $s_i$。原计划每个区块制作 $m$ 块相同的门牌。

但恰好有一个区块的订单丢失了，只剩下其他 $n-1$ 个区块的晶体。

对于每个可能丢失的区块 $\ell$（$1 \le \ell \le n$），求最大的 $k$，使得：

• 能用剩余晶体为其他 $n-1$ 个区块各制作 $k$ 块完整门牌
• 同时至少制作 1 块区块 $\ell$ 的门牌
• 若不存在 $k \ge 0$，输出 -1。

输入格式

第一行为两个整数 $n$ 和 $m$，分别表示需要制作门牌名称的区块数量和每个区块最初要制作的门牌数（$2 \le n \le 2 \times 10^5$，$1 \le m \le 5 \times 10^5$）。

接下来的 $n$ 行每行包含一个字符串 $s_i$，表示第 $i$ 条区块的门牌名称（$1 \le |s_i| \le 5 \times 10^5$）。所有字符串均由大写英文字母组成，门牌名称可能会重复。保证所有的总长度不超过 $5 \times 10^5$。

输出格式

输出一行 $n$ 个整数，第 $\ell$ 个数表示当第 $\ell$ 个区块订单丢失时的最大可行 $k \geq 0$，若无解输出 -1。

样例 1

3 10
NEERC
NERC
NEF

9 9 -1

提示

前两个区块可以通过合理分配晶体，在保证至少重建第三个区块一块门牌的前提下，各自重建 9 块； 第三个区块若订单丢失，则无论如何都无法重建任意一块自身门牌。