퍼즐의 다음 상태를 표현하기

Unrated

한국어

Language

Statement

8퍼즐은 $3 \times 3$ 칸에 1부터 8까지의 조각과 빈칸 하나가 놓인 퍼즐이고, 빈칸은 0으로 나타낸다. 현재 상태가 주어질 때 빈칸을 한 칸 위로 옮긴 상태를 출력하시오. 빈칸을 위로 옮기는 것은 빈칸 바로 위에 있는 조각을 빈칸 자리로 내리는 것과 같다.

세 줄에 걸쳐 각 줄마다 세 정수가 공백을 사이에 두고 주어진다. 아홉 개의 값은 0부터 8까지의 정수가 한 번씩 나타난 것이다.

빈칸을 위로 옮긴 상태를 세 줄에 걸쳐 출력한다. 각 줄의 세 값은 공백을 사이에 두고 출력한다. 빈칸이 첫째 줄에 있어 위로 옮길 수 없으면 Impossible을 출력한다.

Sample input 1

7 1 2
3 4 5
6 0 8

Sample output 1

7 1 2
3 0 5
6 4 8

Sample input 2

0 1 2
3 4 5
6 7 8

Sample output 2

Impossible