안정한 벽

Apollo는 폴리오미노를 이용한 게임을 하고 있다. 폴리오미노는 하나 이상의 정사각형을 변끼리 붙여 하나의 연결된 도형을 만든 것이다. 이 게임은 N개의 폴리오미노를 구멍 없이 하나의 직사각형 모양으로 합치는 게임이다. 각 폴리오미노에는 A부터 Z까지의 서로 다른 문자가 하나씩 붙어 있다.

Apollo는 게임을 끝내고 R개의 행과 C개의 열로 이루어진 직사각형 벽을 만들었다. 그는 사진을 찍어 친구 Selene에게 보냈다. Selene은 벽 사진을 좋아하지만, 그 벽이 안정한 벽이면 더 좋아한다. 벽이 안정하다는 것은 폴리오미노를 하나씩 벽에 추가해서 만들 수 있고, 추가하는 동안 각 폴리오미노가 항상 지지되어 있음을 뜻한다. 폴리오미노가 지지되어 있다는 것은 그 안의 모든 정사각형이 바닥 위에 있거나 바로 아래에 다른 정사각형이 있는 것이다.

Apollo는 자신의 벽이 안정한지 확인하려 하고, 안정하다면 폴리오미노를 추가한 순서를 Selene에게 알려 주어 그것을 증명하려 한다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 두 정수 R과 C가 주어진다. 그다음 R개의 줄이 위에서 아래로 벽을 나타낸다. 각 줄에는 A부터 Z까지의 대문자 C개로 이루어진 문자열이 주어지며, 그 벽의 한 행을 나타낸다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 폴리오미노를 지은 순서를 나타내는 N개의 대문자로 이루어진 문자열이다. 그러한 순서가 여러 개라면 아무거나 출력해도 된다. 벽이 안정하지 않다면 대신 -1을 출력한다.

• 1 ≤ T ≤ 100.
• 1 ≤ R ≤ 30.
• 1 ≤ C ≤ 30.
• 두 폴리오미노가 같은 문자로 표시되는 경우는 없다.
• 입력은 문제에 설명된 규칙에 따라 항상 올바르다.

샘플 케이스 #1에서 ZOMA도 가능한 답이다.

샘플 케이스 #2와 샘플 케이스 #3에서는 벽이 안정하지 않으므로 답은 -1이다.

샘플 케이스 #4에서 가능한 답은 EDCBA뿐이다.