27737번 - 버섯 농장 서브태스크

농부 해강이는 $N \times N$ 칸으로 이루어진 나무판에서 버섯 농사를 짓는다. 나무판은 버섯이 자랄 수 있는 칸과 없는 칸으로 이루어져 있다.

해강이는 $M$개의 버섯 포자를 가지고 있다. 버섯 포자는 버섯이 자랄 수 있는 칸에만 심을 수 있다.

각 버섯 포자는 포자가 심어진 칸을 포함해 최대 $K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯을 자라게 한다. 이때 연결된 칸은 상하좌우로 적어도 한 변을 공유하는 칸들의 집합이라고 정의한다.

또한 한 칸에 버섯 포자를 여러 개 겹쳐서 심을 수 있으며, 만약 $x$개의 버섯 포자를 겹쳐 심으면 포자가 심어진 칸을 포함해 최대 $x \times K$개의 연결된 (버섯이 자랄 수 있는) 칸에 버섯이 자란다.

<그림 1> $K = 4$일 때 버섯이 자라는 모습이다.

<그림 2> $K = 10$일 때 버섯이 자라는 모습이다.

해강이는 버섯 포자를 심을 때 최소 개수로만 심으려고 한다. 해강이가 농사가 가능할지 판단하고, 농사가 가능하다면 남은 버섯 포자의 개수를 출력하시오.

버섯 포자를 하나라도 사용하고 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능하다고 정의한다.

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 나무판의 각 칸의 상태가 공백으로 구분되어 주어진다.

버섯이 자랄 수 있는 칸은 0, 버섯이 자랄 수 없는 칸은 1로 주어진다.

만약 버섯 농사가 불가능하면 IMPOSSIBLE을 출력한다.

버섯 농사가 가능하다면, POSSIBLE을 출력하고 다음 줄에 남은 버섯 포자의 개수를 출력한다.

• $1 \leq N \leq 100$
• $0 \leq M \leq 1\,000\,000$
• $1 \leq K \leq 10^8$
• $N, M, K$는 모두 정수이다.