Hangman 2

John likes to play Hangman, the word guessing game. Today, however, he got really mad at the game. He arrived at the configuration spi_e, where finding the solution requires pure luck (solutions include spice, spike, spine and spire).

John is frustrated and argues that some words should never be chosen initially, namely words that differ from other words by at most two letters.

Given a list of N distinct words, all of length K, print in alphabetical order those words from which no other word can be obtained by substituting at most two letters.

Unlike classic Hangman, in this problem when John guesses a letter only one instance of the letter is revealed. For example, spi_e could hypothetically resolve to spise, whereas in classic Hangman guessing s would reveal both s's, so spi_e would be an invalid configuration.

The first line contains an integer T, the number of tests. The T tests follow. Each of them has the following structure:

• The first line contains two integers N and K.
• Each of the following N lines contains a word of K small English letters.

For each of the T tests print one line with the following structure:

• A sequence of N characters: the ith character is 1 if the ith word can be obtained by substituting at most two letters from another word, or 0 if not and the word can be played in the game.

$1 \le T \le 10$

$1 \le N \cdot K \le 4.5 \cdot 10^4$

spi_e could lead to spike, spine and spire.

ch_ir could lead to chair and choir.

cho__ could lead to choir and chore.

The only word that can be used in the game is: speed.