Missing Piece 2001

Wiltin' Badley는 숫자 조각을 밀어서 맞추는 옛날 퍼즐을 다시 만들어 Missing Piece 2001이라는 이름으로 내놓았다. 이 제품에는 퍼즐이 얼마나 어려운지 미리 알려 주는 프로그램이 딸려 온다. 플레이어가 처음 배치와 목표 배치를 입력하면 프로그램은 정해진 횟수 안에 퍼즐을 맞출 수 있는지 판정하고, 맞출 수 있으면 목표 배치를 만드는 데 필요한 최소 이동 횟수를 알려 준다. 당신이 이 프로그램을 만들어야 한다.

판의 크기, 맞추고 싶은 이동 횟수, 처음 배치, 목표 배치를 모두 사용자가 입력한다. 크기가 다른 판도 따로 팔기 때문에 프로그램은 어떤 크기든 처리해야 한다.

빈 칸 X와 상하좌우로 맞닿은 조각 하나를 빈 칸 쪽으로 밀면 한 번의 이동이다. 빈 칸과 맞닿지 않은 조각은 움직일 수 없고, 이동 방향은 위, 아래, 왼쪽, 오른쪽뿐이다.

입력은 데이터 집합이 최대 10개 이어진 형태이고, 적어도 하나는 주어진다. 데이터 집합 사이에 빈 줄은 없다.

각 데이터 집합은 네 부분으로 이루어진다.

1. 시작 줄: START D N 형식의 한 줄이며, $3 \le D \le 10$, $0 \le N \le 15$이다.
2. 처음 배치: $D \times D$ 행렬로, 1 이상 $D^2 - 1$ 이하의 정수와 빈 칸을 뜻하는 X가 들어간다. 퍼즐을 풀기 전 판의 상태이다.
3. 목표 배치: 같은 형식의 $D \times D$ 행렬이며, 퍼즐을 맞췄다고 인정하는 판의 상태이다.
4. 끝 줄: END 한 줄

$D$는 판의 한 변의 길이이고, $N$은 플레이어가 그 안에 퍼즐을 맞추고 싶은 이동 횟수이다. 두 배치 모두 1부터 $D^2 - 1$까지의 수가 빠짐없이 한 번씩 들어가고 빈 칸 X는 정확히 하나이며, 빠진 수나 겹치는 수는 없다.

데이터 집합마다 한 줄씩 출력하고, 출력 사이에는 빈 줄을 하나 넣는다.

정해진 이동 횟수 안에 목표 배치를 만들 수 있으면 판정 문자열은 SOLVABLE이고, 뒤따르는 수는 목표 배치를 만드는 데 필요한 최소 이동 횟수이다. 만들 수 없으면 판정 문자열은 NOT SOLVABLE이고, 뒤따르는 수는 입력으로 주어진 $N$을 그대로 적는다.

각 줄의 형식은 다음과 같다.

<판정 문자열> WITHIN <이동 횟수> MOVES

WITHIN과 MOVES는 있는 그대로 출력하고, 이동 횟수가 1일 때도 MOVES라고 적는다.