14263번 - 카드 놓기

문제

영선이는 카드와 그리드를 가지고 놀고 있다. 각각의 카드는 직사각형 모양이며, 색칠되어져 있다. 두 카드가 같은 색을 가지는 경우는 없으며, 크기도 카드마다 다를 수 있다.

영선이는 한 번에 카드 하나씩 그리드 위에 올려놓는다. 카드를 올려놓을 때, 그리드의 변과 평행이 되게 카드를 올려놓아야 한다. 따라서, 직사각형은 그리드의 칸을 덮게 된다. 또, 카드는 겹쳐서 놓을 수 있다. 카드가 놓이면서 어떤 카드를 완전히 가리는 경우는 없다.

카드를 다 놓은 다음, 위에서 바라본 결과가 주어진다. 이때, 카드를 놓은 순서를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 그리드의 크기 N과 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 그리드에 놓여진 카드의 색이 주어진다. 카드의 색은 알파벳 소문자('a'-'z'), 대문자('A'-'Z'), 숫자('0'-'9') 중 하나이며, '.'는 빈 칸이다.

출력

첫째 줄에 카드를 놓은 순서를 출력한다. 만약 가능한 순서가 여러 가지라면, 사전순으로 앞서는 것을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다.

제한

힌트