P14782 [NERC 2025] Alphabet City

Al 是字母城的一位城市规划师，今天他的任务是为 $n$ 条城市街道准备路牌。在字母城，路牌仅由大写、完全相同的金属字母模印的街道名称组成。例如，如果在夜间有人偷偷交换了 NERC 街和 NEF 街路牌上的第一个字母，第二天不会有人发现异常，因为两个牌子上的字母 'N' 是相同的。 Al 计划为每条街道放置 $m$ 个路牌，并且他已经从金属加工厂订购了每个街道名称所需数量的黄铜字母。然而，在订单到达前一个小时，Al 接到了工厂经理的电话，带来了一个毁灭性的消息：他们丢失了街道名称清单中的一项！为了缓解这个问题，Al 决定暂时为订单未丢失的每条街道尽可能多地放置路牌，并用剩余的字母为订单丢失的那条街道至少制作一个路牌。 形式化地说，如果 $s_1, \dots, s_n$ 是街道名称，$\ell$ 是订单中丢失项的索引，Al 想知道最大的整数 $k$，使得从 $m$ 份 $s_1, \dots, s_{\ell-1}, s_{\ell+1}, \dots, s_n$ 的所有字母中，可以拼凑出 $k$ 份 $s_1, \dots, s_{\ell-1}, s_{\ell+1}, \dots, s_n$ 以及至少一份 $s_\ell$；或者确定对于任何非负整数 $k$ 这样的拼凑都是不可能的。Al 仍然不知道具体丢失了哪一项。请编写一个程序，给定 $m$ 和所有街道名称，对于每个 $\ell \in \{1, 2, \dots, n\}$，输出 $k$ 的最大值；如果这样的拼凑不可能，则输出 $-1$。

第一行包含两个整数 $n$ 和 $m$，分别表示需要制作路牌的街道数量和 Al 最初订购的每个街道名称的副本数 ($2 \le n \le 2 \cdot 10^5$；$1 \le m \le 5 \cdot 10^5$)。接下来的 $n$ 行，每行包含一个字符串 $s_i$ —— 街道名称 ($1 \le |s_i| \le 5 \cdot 10^5$)。所有这些名称都由大写英文字母组成。部分或全部名称可能相同。保证所有街道名称的长度之和不超过 $5 \cdot 10^5$。

输出 $n$ 个整数，第 $\ell$ 个表示最大的整数 $k$，使得 $m \times s_1, \dots, m \times s_{\ell-1}, m \times s_{\ell+1}, \dots, m \times s_n$（其中 $m \times s$ 表示街道名称 $s$ 的 $m$ 个副本）的字母足够拼凑出 $k \times s_1, \dots, k \times s_{\ell-1}, 1 \times s_\ell, k \times s_{\ell+1}, \dots, k \times s_n$。如果对于给定的 $\ell$ 值，这些字母不足以拼凑出任何整数 $k \ge 0$ 的情况，则输出 $-1$。

翻译由 DeepSeek V3 完成