슬라이딩 퍼즐 마스터

철수는 슬라이딩 퍼즐의 마스터이다.

슬라이딩 퍼즐은 $N$행 $M$열의 격자 모양이다. 이 중 한 칸은 비어있고, 나머지 칸들은 $1$부터 $N\times M-1$까지의 수들로 채워져 있다.

슬라이딩 퍼즐은 각 시행마다 빈칸과 인접한 어떤 조각에 대해, 그 조각과 빈칸의 위치를 바꿀 수 있다. 인접한 방향은 상하좌우, 네 방향이다.

어느 날 영희가 나타나 슬라이딩 퍼즐을 이용하여 $(N\times M)!$가지의 모든 배치를 한 번씩 등장하게 만들어 보라고 철수를 도발했다. 철수는 아무리 생각해도 기존의 규칙만으로는 힘들 것 같다고 생각했다.

그래서 철수는 꼼수를 생각해 내었다. 바로 영희의 집중이 흐려진 지금, 몰래 퍼즐의 두 조각을 빠르게 교환하는 것이다. 인접하지 않은 두 조각을 바꾼다면 티가 많이 나서 영희가 알아차리므로 인접한 두 조각만을 교환해야 한다.

정리하면, 철수는 매번 다음 두 시행 중 하나를 골라서 시행하는 것을 반복하면 된다.

• 기존 슬라이딩 퍼즐의 시행
• 인접한 두 조각을 교환하는 시행

안타깝게도 꼼수를 생각하느라 철수는 힘이 다 빠졌다. 철수를 도와 모든 배치를 만들어보자.

철수에게 처음 주어진 슬라이딩 퍼즐은 가장 오른쪽 아래의 칸이 비어있고, 나머지는 $i$번째 행의 $j$번째 열에 $(i-1)\times M + j$가 적힌 조각이 배치된 상태이다.

슬라이딩 퍼즐의 빈칸은 #으로 표현한다.

첫째 줄에 정수 $N$과 $M$이 공백을 사이에 두고 주어진다. ($2\le N\times M\le 9$)

첫째 줄부터 $N$번째 줄까지 철수에게 주어진 퍼즐의 상태를 출력한다.

이후 철수가 시행을 통해 바꾼 퍼즐의 새로운 배치 상태 $(N\times M)!-1$가지를 순서대로 개행 문자로 나누어 출력한다.

각 배치 상태마다 $N$개의 줄에 걸쳐 길이 $M$의 각 행을 출력한다. 이때, 각 행은 $M$개의 문자를 공백 없이 붙여 출력한다.

가능한 방법이 여러 가지인 경우, 그중 아무 방법이나 선택하여 조건에 맞게 출력하면 된다.