题目描述

John 喜欢玩 Hangman，也就是猜单词游戏。但是今天他对这个游戏非常恼火。

例如，游戏过程中可能出现如下局面：

spi_e

此时可能的答案包括：

spice
spike
spine
spire

John 认为，这种局面完全依赖运气。因此，有些单词一开始就不应该被选作答案。具体来说，如果某个单词与另一个单词最多只相差两个字母，那么这个单词就不应该被选作初始答案。

现在给定 $N$ 个互不相同、长度均为 $K$ 的小写英文单词。对于每个单词，判断它是否可以通过把另一个单词中的至多两个字符替换掉得到。

也就是说，对于第 $i$ 个单词，如果存在另一个单词与它的汉明距离不超过 $2$，则输出 1；否则输出 0，表示这个单词可以被安全地用于游戏。

说明

与经典 Hangman 不同，本题中当 John 猜中一个字母时，只会揭示该字母的一个出现位置，而不是揭示所有相同字母的位置。

例如，spi_e 理论上可以对应 spise；而在经典 Hangman 中，如果猜出了 s，所有 s 都会被揭示，因此这种局面不会合法。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组测试数据。每组测试数据格式如下：

第一行包含两个整数 $N,K$。

接下来 $N$ 行，每行包含一个长度为 $K$ 的小写英文单词。

输出格式

对于每组测试数据，输出一行长度为 $N$ 的 01 字符串。

其中第 $i$ 个字符为：

• 1：如果第 $i$ 个单词可以由另一个单词替换至多两个字母得到；
• 0：否则，这个单词可以被用于游戏。

数据范围与约定

• $1\le T\le 10$；
• 对于每组测试数据，$1\le N\cdot K\le 3\cdot 10^4$；
• 所有单词互不相同；
• 所有单词均由小写英文字母组成。

子任务

样例

输入

1
7 5
spike
speed
choir
spine
chair
chore
spire

输出

1011111

样例解释

• spi_e 可以对应 spike、spine 和 spire；
• ch_ir 可以对应 chair 和 choir；
• cho__ 可以对应 choir 和 chore。

唯一可以安全用于游戏的单词是 speed。

难度评估

难度：提高+ / 省选-，约 CF 2100～2300，建议标为 2200。

题目本质是：给定若干等长字符串，判断每个字符串是否存在另一个字符串与它的汉明距离不超过 $2$。

直接枚举所有单词对并逐位比较是 $O(N^2K)$，在 $N\cdot K\le 3\cdot 10^4$ 时仍然可能过大。常见做法是根据 $K$ 与 $N$ 的大小做分治或混合策略：当 $K$ 较小时，可以枚举删除/通配 1～2 个位置后的模式并哈希；当 $K$ 较大时，$N$ 会相对较小，可以对单词对做较快的逐位比较并提前停止。

这题思维不算特别重，但需要把 $N\cdot K$ 的限制利用好，并且避免哈希冲突、重复计数以及把自身误判为匹配对象。作为省选前中档字符串题比较合适。