题目描述

约翰有 $N$ 个牛棚，编号 $1∼N$。

每个牛棚都要派出一个 $C$ 头奶牛的小队去参加户外集会。

奶牛有两种品种，一种是根西牛（用 G 表示），另一种是荷斯坦牛（用 H 表示）。

每个小队都可以用一个由 G 和 H 组成的长度为 $C$ 的字符串来表示，字符串中的第 $i$个字符用来表示队伍中处于第 $i$ 位的奶牛的品种。

两个小队的差异值定义为：统计代表两个小队的字符串在多少个位置上的字符不同，这个数量就是两个小队的差异值。

对于 $1∼N$ 中的每个 $t$，请你计算第 $t$ 个牛棚派出的小队与任何其它小队之间的最大差异值。

输入格式

第一行包含两个整数 $C$ 和 $N$。

接下来 $N$ 行，每行包含一个由 G 和 H 组成的长度为 $C$ 的字符串，对应一个小队。

输出格式

共 $N$ 行，第 $i$ 行输出第 $i$ 个牛棚派出的小队与任何其它小队之间的最大差异值。

5 3
GHGGH
GHHHH
HGHHG

5
3
5

提示

$1≤C≤18,$
$2≤N≤10^5$

样例解释

第一队和第三队的差异值为 $5$。

第二队和第三队的差异值为 $3$。