Al 是 Alphabet City 的一名城市设计师,今天他们的任务是为 $$$n$$$ 城市街道准备标志。在字母城,街道标志只是由街道名称组成,街道名称由大写相同的英文金属字母组成。例如,如果有人在夜间偷偷地交换了 NERC 街和 NEF 街的第一个字母,那么第二天没有人会看到差异,因为两个标志上的字母“N”是相同的。
Al 计划在每条街道上放置 $$$m$$$ 标志,并且他们已经从冶金厂为每条街道名称订购了所需数量的黄铜字母。然而,在订单到达前一小时,阿尔接到了工厂经理的电话,带来了一个毁灭性的消息:他们丢失了街道名称列表中的一项!为了缓解这个问题,阿尔决定暂时在每条没有丢失秩序的街道上放置尽可能多的标志,并利用剩下的字母,为秩序丢失的街道准备至少一个标志。
形式上,如果 $$$s_1, \ldots, s_n$$$ 是街道名称,$$$\ell$$$ 是订单中缺失项目的索引,则 Al 对最大整数 $$$k$$$ 感兴趣,这样就可以从 $$$s_1, \ldots, s_{\ell - 1} 的 $$$m$$$ 副本的所有字母中获得最大整数 $$$k$$$, s_{\ell + 1}, \ldots, s_n$$$,组成 $$$k$$$ 副本 $$$s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$$$ 以及至少一份 $$$s_\ell$$$ 副本,或确定这样的组合对于任何非负数都是不可能的$$$k$$$。
Al 仍然不知道丢失了哪些物品。编写一个程序,给定 $$$m$$$ 和所有街道名称,对于每个 $$$\ell \in \{1, 2, \ldots, n\}$$$ 打印 $$$k$$$ 的最大值,如果这样的组合不可能,则打印 $$$-1$$$ 的最大值。
输入
第一行由两个整数 $$$n$$$ 和 $$$m$$$ 组成,表示 Alphabet City 中需要标志的街道数量以及 Al 最初订购的每个街道名称的份数($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 5 \cdot 10^5$$$)。接下来的 $$$n$$$ 行均包含一个字符串 $$$s_i$$$ — 街道名称 ($$$1 \le \left|s_i\right| \le 5 \cdot 10^5$$$)。所有这些名字都是由大写英文字母组成的。这些名称的部分或全部 可能 一致。保证所有街道名称的长度总和不超过$$$5 \cdot 10^5$$$。
输出
打印 $$$n$$$ 个整数,其中第 $$$\ell$$$ 表示最大整数 $$$k$$$,使得 $$$m \times s_1$$$, ..., $$$m \times s_{\ell - 1}$$$, $$$m \times s_{\ell + 1}$$$, ..., $$$m \times s_n$$$ (其中 $$$m \times s$$$ 表示 $$$m$$$ 街道名称 $$$s$$$ 的副本)足以组成 $$$k \times s_1$$$, ..., $$$k \times s_{\ell - 1}$$$, $$$1 \times s_\ell$$$, $$$k \times s_{\ell + 1}$$$, ..., $$$k \times s_n$$$。如果对于给定值 $$$\ell$$$,这些字母不足以满足任何整数 $$$k \ge 0$$$,则打印 $$$-1$$$。
示例
输入复制
3 10NEERCNERCNEF
输出复制
9 9 -1
输入复制
4 4LENSETENSENSELESSNESSESLENSE
输出复制
3 -1 0 3