CF2181A Alphabet City

Al 是 Alphabet City 的一名城市设计师，今天他的任务是为 $n$ 条城市街道准备招牌。在 Alphabet City，街道标牌仅由街道名称组成，这些名称全都由一模一样的英文字母金属牌印制而成。例如，如果在夜间有人偷偷交换了 NERC 街和 NEF 街招牌上的首字母，第二天没人会发现差别，因为两块牌上的字母 ‘N’ 完全一样。 Al 计划在每条街道上都放置 $m$ 个招牌，并且他已经从冶金厂为每个街道名称订购了所需数量的铜牌。然而，就在订单到货前一小时，冶金厂的经理打来电话，带来了一个令人沮丧的消息：他们丢失了一个街道名称的订单！为了缓解这个问题，Al 决定暂时为订单未丢失的每条街道尽可能多制作招牌，并用剩下的字母，尝试为丢失订单的那条街道至少制作一个招牌。 具体来说，若街道名称为 $s_1, \ldots, s_n$，$\ell$ 表示丢失订单的编号，则 Al 关心的是最大的整数 $k$，使得可以用 $s_1, \ldots, s_{\ell-1}, s_{\ell+1}, \ldots, s_n$ 的 $m$ 份字母，制作出 $s_1, \ldots, s_{\ell-1}, s_{\ell+1}, \ldots, s_n$ 各 $k$ 块招牌，并且还能至少制作一块 $s_\ell$ 的招牌；或者判定对于所有非负整数 $k$，该目标都无法实现。 Al 还不知道丢失的是哪一项。请编写程序，给定 $m$ 和所有街道名称，对于每个 $\ell \in \{1, 2, \ldots, n\}$，输出最大的 $k$，若无解则输出 $-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$ 个整数表示最大整数 $k$，使得用 $m \times s_1,\ldots,m \times s_{\ell-1},m \times s_{\ell+1},\ldots,m \times s_n$ 的字母可以拼出 $k$ 份 $s_1,\ldots,s_{\ell-1},s_{\ell+1},\ldots,s_n$，并且可以再拼出至少一个 $s_\ell$；如果对于该 $\ell$，任意 $k \ge 0$ 都不能满足条件，则输出 $-1$。

由 ChatGPT 5 翻译