题目描述

Al 是字母城的城市设计师，今天他要为 $n$ 条街道准备路牌。在字母城里，路牌由大写英文字母金属牌拼成，相同字母的金属牌完全一样。举个例子：夜里有人偷偷交换了 NERC 路和 NEF 路路牌的首字母，第二天没有人能看出来区别，因为字母 'N' 是一模一样的。

Al 计划为每条街道制作 $m$ 块路牌，并且已经向冶金厂订购了对应数量的字母。但订单送达前一小时，工厂经理打来电话，带来一个坏消息：街道名称清单里弄丢了其中一项。 为了补救，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$，并且额外至少拼出 $1$ 份 $s_\ell$。 如果不存在任何非负整数 $k$ 满足条件，输出 $-1$。

Al 还不知道弄丢的是哪一项。给定 $m$ 和全部街道名称，对每个 $\ell \in \{1,2,\dots,n\}$，输出最大的 $k$；不可能则输出 $-1$。

输入格式

第一行两个整数 $n,m$，代表街道数量，以及最初计划为每条街道制作的路牌份数（$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$ 份除 $s_\ell$ 以外所有街道的字母，能不能拼出 $k$ 份其余所有街道 + $1$ 份 $s_\ell$。无法满足则输出 $-1$。

3 10
NEERC
NERC
NEF

9 9 -1

4 4
LENSE
TEN
SENSELESSNESSES
LENSE

3 -1 0 3

原题链接

原题链接