행맨 2

존은 단어 맞히기 게임인 행맨을 즐겨 한다. 그런데 오늘은 이 게임 때문에 몹시 화가 났다. 그가 마주한 상황은 spi_e였고, 여기서 정답을 찾으려면 순전히 운이 필요하다 (정답은 spice, spike, spine, spire가 될 수 있다).

존은 답답해하며, 다른 단어와 최대 두 글자만 다른 단어는 처음부터 고르면 안 된다고 주장한다.

길이가 모두 K인 서로 다른 단어 N개가 주어진다. 이 중에서 최대 두 글자를 바꿔 다른 단어를 만들 수 없는 단어들을 사전순으로 출력하라.

고전 행맨과 달리 이 문제에서는 존이 글자 하나를 맞히면 그 글자가 한 번만 드러난다. 예를 들어 spi_e는 spise가 될 수 있지만, 고전 행맨에서 s를 맞히면 두 s가 모두 드러나므로 spi_e는 올바른 상태가 아니다.

첫 줄에는 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 다음과 같다.

• 첫 줄에는 정수 N과 K가 주어진다.
• 이어지는 N줄에는 길이 K인 영어 소문자 단어가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 한 줄을 출력한다. 이 줄은 N개의 문자로 이루어지며, i번째 문자는 i번째 단어가 다른 단어에서 최대 두 글자를 바꿔 얻어질 수 있으면 1, 그렇지 않고 게임에서 사용할 수 있으면 0이다.

$1 \le T \le 10$

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

spi_e는 spike, spine, spire로 이어질 수 있다.

ch_ir는 chair와 choir로 이어질 수 있다.

cho__는 choir와 chore로 이어질 수 있다.

이 게임에서 사용할 수 있는 단어는 speed뿐이다.