CF2181A.Alphabet City

Al is an urban designer in Alphabet City, and today their task is to prepare signs for $n$ city streets. In Alphabet City, the street signs simply consist of the street names composed of capital identically stamped English metal letters. For instance, if, during nighttime, someone sneakily exchanges the first letters on NERC street and on NEF street, the next day nobody will see the difference as the letter 'N' is identical on both signs.

Al is planning to put $m$ signs on each street, and they have already ordered the required number of brass letters for each of the street names from the metallurgical plant. However, one hour before the order arrived, Al got a call from the plant's manager with a devastating piece of news: they lost one of the items from the list of street names! To mitigate the issue, Al decided for now to put as many signs as possible on each street whose order was not lost, and, with the leftover letters, to prepare at least one sign for the street whose order was lost.

Formally, if $s_1, \ldots, s_n$ are the street names, and $\ell$ is the index of the missing item from the order, Al is interested in the maximum integer $k$ such that it is possible, from all the letters of $m$ copies of $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$, to compose $k$ copies of $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$ and additionally at least one copy of $s_\ell$, or to determine that such a composition is impossible for any non-negative $k$.

Al still does not know which of the items was lost. Write a program that, given $m$ and all street names, for each $\ell \in {1, 2, \ldots, n}$ prints the maximum value of $k$, or $-1$ if such a composition is impossible.

阿尔是字母城的一名城市规划师，今天他的任务是为该城市的 $n$ 条街道制作路牌。在字母城，路牌仅由街道名称构成，且每个字母均使用完全相同的、大写的英文字母金属印章冲压而成。例如，若有人在夜间偷偷将“NERC 街”和“NEF 街”的路牌首字母互换，则第二天无人能察觉差异，因为两个路牌上的字母 'N' 完全相同。

阿尔计划在每条街道上安装 $m$ 个路牌，并已向冶金工厂订购了每条街道名称所需数量的黄铜字母。然而，在订单送达前一小时，阿尔接到工厂经理打来的电话，告知了一个灾难性的消息：他们丢失了街道名称清单中的某一项！为缓解这一问题，阿尔决定：对未丢失订单的街道，尽可能多地安装路牌；并利用剩余的字母，至少为那条订单丢失的街道制作一个路牌。

形式化地，设 $s_1, \ldots, s_n$ 为各街道名称，$\ell$ 为订单中丢失项的下标（即 $s_\ell$ 对应的订单丢失），阿尔希望找出最大的整数 $k$，使得：利用所有未丢失订单的街道名称（即 $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$）各自 $m$ 份所含的全部字母，能够拼出 $k$ 份这些未丢失街道的名称（即 $k$ 份 $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$），并且额外至少拼出一份丢失街道的名称 $s_\ell$；或者判定：对任意非负整数 $k$，这样的拼组均不可能实现。

目前阿尔尚不清楚哪一项订单丢失了。请编写一个程序：给定 $m$ 和全部街道名称，对每个 $\ell \in \{1, 2, \ldots, n\}$，输出对应的最大 $k$ 值；若这样的拼组对任意非负整数 $k$ 均不可能实现，则输出 $-1$。

The first line consists of two integers $n$ and $m$, denoting the number of streets in Alphabet City for which the signs are needed and the number of copies of each street name that Al initially ordered ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 5 \cdot 10^5$). Each of the next $n$ lines consists of one string $s_i$ — the street name ($1 \le \left|s_i\right| \le 5 \cdot 10^5$). All these names are composed of capital English letters. Some or all of these names may coincide. It is guaranteed that the sum of the lengths of all the street names does not exceed $5 \cdot 10^5$.

第一行包含两个整数 $n$ 和 $m$，分别表示 Alphabet 城需要路牌的街道数量，以及 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$。

Print $n$ integers, the $\ell$-th of them denoting the maximum integer $k$ such that the letters of $m \times s_1$, ..., $m \times s_{\ell - 1}$, $m \times s_{\ell + 1}$, ..., $m \times s_n$ (where $m \times s$ denotes $m$ copies of street name $s$) are enough to compose $k \times s_1$, ..., $k \times s_{\ell - 1}$, $1 \times s_\ell$, $k \times s_{\ell + 1}$, ..., $k \times s_n$. If, for the given value of $\ell$, these letters are insufficient for any integer $k \ge 0$, print $-1$ instead.

输出 $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$ 的整数 $k$，则输出 $-1$。