접착된 격자

슬라이딩 퍼즐은 직사각형 격자 위에 놓인 정사각형 타일로 이루어진다. 격자의 칸 중 정확히 하나는 비어 있다. 빈 칸의 위, 아래, 왼쪽, 오른쪽에 있는 타일을 빈 칸으로 옮길 수 있고, 그 이동은 되돌릴 수도 있다.

각 타일에는 고유한 번호가 적혀 있다 (그림 G.1). 퍼즐을 풀려면 이동을 반복해서 타일 번호가 왼쪽에서 오른쪽, 위에서 아래 방향으로 오름차순이 되도록 만들고, 빈 칸을 오른쪽 아래 위치에 두어야 한다 (그림 G.2). 모든 퍼즐이 이렇게 풀리는 것은 아니다.

그림 G.1: 3행 4열 슬라이딩 퍼즐. 샘플 입력 1에 해당한다.	그림 G.2: 그림 G.1의 퍼즐을 푼 모습.	그림 G.3: 초록색 끈끈한 물질로 덮인 고정 타일이 있는 슬라이딩 퍼즐. 풀 수 있는 경우이며 샘플 입력 3에 해당한다.

집 정리를 하던 중, 차고의 고블린들이 내기를 제안한다. 그들의 슬라이딩 퍼즐을 모두 풀면 물건이 가득 든 빛나는 상자를 가져도 된다. 그런데 고블린들이 일부 타일을 바닥에 붙여 놓았다. 붙은 타일은 움직이지 않는다 (그림 G.3).

모든 슬라이딩 퍼즐은 다음 성질을 가진다.

• 빈 칸은 오른쪽 아래 위치에 있다.
• 붙은 타일은 모두 올바른 위치에 있다.
• 움직일 수 있는 타일마다, 빈 칸을 그 타일이 있는 위치에 둘 수 있는 이동 순서가 있다.
• 붙은 타일에서 출발해 위, 아래, 왼쪽, 오른쪽으로 한 칸씩 이동하면서 붙은 타일만 거쳐 퍼즐의 가장자리에 닿을 수 있다. 즉 움직일 수 있는 타일에 둘러싸인 붙은 타일은 없다.

주어진 슬라이딩 퍼즐을 풀 수 있는지 판단하라.

첫 줄에 격자의 높이와 너비를 나타내는 두 정수 $h$와 $w$ ($1 \le h,w \le 500$)가 주어진다.

다음 $h$개 줄에는 각각 $w$개의 문자가 주어지며, 각 문자는 '.' 또는 '#'이다. 오른쪽 아래 문자는 빈 칸의 위치이며 항상 '.'이다. 그 밖의 '.'은 움직일 수 있는 타일을, '#'은 붙은 타일을 뜻한다.

그다음 $h$개 줄에는 각각 $w$개의 정수 $a_{i,j}$ ($1 \le i \le h$, $1 \le j \le w$, $0 \le a_{i,j} \le h \cdot w - 1$)가 주어진다. 오른쪽 아래 정수 $a_{h,w}$는 0이며 빈 칸을 나타낸다. 나머지 $a_{i,j}$는 위치 $(i,j)$에 있는 타일의 번호이다. 모든 $a_{i,j}$에는 $0, 1, \dots, h \cdot w - 1$이 각각 한 번씩 나타난다.

퍼즐을 풀 수 있으면 possible을, 풀 수 없으면 impossible을 출력한다.