Al 是 Alphabet City 的一名城市规划师，今天他的任务是为 $n$ 条城市街道制作路牌。在 Alphabet City，路牌仅由大写、相同压制的英文金属字母组成的街道名称构成。例如，如果在夜间，有人偷偷交换了 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$，表示 Alphabet City 中需要路牌的街道数量，以及 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$。

样例

输入样例 1

3 10
NEERC
NERC
NEF

输出样例 1

9 9 -1

输入样例 2

4 4
LENSE
TEN
SENSELESSNESSES
LENSE

输出样例 2

3 -1 0 3