#include <iostream>
#include <string>
#include <fstream>

class PathFinder{
private:
	int in_x, in_y, o_x, o_y, wave;
	int **lab;
	int **path;
	int l_row, l_col;
	std::string savefile;
public:
	PathFinder(std::string filename, std::string savefile);
	void DoWave(int x, int y, int c_wave);
	void FindMinimal(int x, int y, int c_wave);
	void MergeIt();
	void SaveIt();
	~PathFinder();
};

PathFinder::PathFinder(std::string filename, std::string savefile){
	this->savefile = savefile;
	std::ifstream fin(filename.c_str());
	if (!fin.is_open()){
		std::cout << "File cannot be open!" << std::endl;
		exit(0);
	}
	else{
		fin >> l_row >> l_col;

		lab = new int*[l_col];
		for (int i = 0; i < l_col; i++){
			lab[i] = new int[l_row];
		}

		path = new int*[l_col];
		for (int i = 0; i < l_col; i++){
			path[i] = new int[l_row];
		}

		for (int i = 0; i < l_col; i++){
			for (int j = 0; j < l_row; j++){
				fin >> lab[i][j];
				if (lab[i][j] == 2){
					in_x = i;
					in_y = j;
					lab[i][j] = 0;
				}
				if (lab[i][j] == 3){
					o_x = j;
					o_y = i;
					lab[i][j] = 0;
				}
				if (lab[i][j] == 1){
					lab[i][j] = -1;
				}
			}
		}
	}
	fin.close();
	DoWave(in_x, in_y, 0);
}

void PathFinder::DoWave(int x, int y, int c_wave){
	lab[x][y] = c_wave;
	if (y + 1 < l_row){
		if ((lab[x][y + 1] == 0) || ((lab[x][y + 1] != -1) && (lab[x][y + 1] > c_wave))){
			DoWave(x, y + 1, c_wave + 1);
		}
	}
	if (x + 1 < l_col){
		if ((lab[x + 1][y] == 0) || ((lab[x + 1][y] != -1) && (lab[x + 1][y] > c_wave))){
			DoWave(x + 1, y, c_wave + 1);
		}
	}
	if (y - 1 >= 0){
		if ((lab[x][y - 1] == 0) || ((lab[x][y - 1] != -1) && (lab[x][y - 1] > c_wave))){
			DoWave(x, y - 1, c_wave + 1);
		}
	}
	if (x - 1 >= 0){
		if ((lab[x - 1][y] == 0) || ((lab[x - 1][y] != -1) && (lab[x - 1][y] > c_wave))){
			DoWave(x - 1, y, c_wave + 1);
		}
	}
}

void PathFinder::SaveIt(){
	if (lab[o_y][o_x] > 0){
		FindMinimal(o_y, o_x, lab[o_y][o_x]);
		std::cout << "possible" << std::endl;
		MergeIt();
		std::ofstream file;
		file.open(savefile);
		for (int i = 0; i < l_col; i++){
			for (int j = 0; j < l_row; j++){
				if ((i == in_x) && (j == in_y)){
					file << 'S';
				}
				else if ((i == o_y) && (j == o_x)){
					file << 'F';
				}
				else{
					if ((lab[i][j] == 666)){
						file << ".";
					}
					else if (lab[i][j] == 0){
						file << " ";
					}
					else{
						file << '1';
					}
				}
			}
			file << std::endl;
		}
		file.close();
	}
	else{
		std::cout << "Unpossible" << std::endl;
	}
}

void PathFinder::FindMinimal(int x, int y, int c_wave){
	if (path[x][y] != 0){
		path[x][y] = 666;
		if (y + 1 < l_row && ((lab[x][y + 1] == 0) || ((lab[x][y + 1] != -1) && (lab[x][y + 1] < c_wave)))){
			FindMinimal(x, y + 1, lab[x][y]);
		}
		else if (x + 1 < l_col && ((lab[x + 1][y] == 0) || ((lab[x + 1][y] != -1) && (lab[x + 1][y] < c_wave)))){
			FindMinimal(x + 1, y, lab[x][y]);
		}
		else if (y - 1 >= 0 && ((lab[x][y - 1] == 0) || ((lab[x][y - 1] != -1) && (lab[x][y - 1] < c_wave)))){
			FindMinimal(x, y - 1, lab[x][y]);
		}
		else if (x - 1 >= 0((lab[x - 1][y] == 0) || ((lab[x - 1][y] != -1) && (lab[x - 1][y] < c_wave)))){
			FindMinimal(x - 1, y, lab[x][y]);
		}
	}
}

void PathFinder::MergeIt(){
	for (int i = 0; i < l_col; i++){
		for (int j = 0; j < l_row; j++){
			if (lab[i][j]>0){
				if (path[i][j] != 666)
					lab[i][j] = 0;
				else
					lab[i][j] = 666;
			}
		}
	}
}

PathFinder::~PathFinder(){
	for (int i = 0; i < l_col; i++){
		delete[](lab[i]);
		delete[](path[i]);
	}
	delete[](lab);
	delete[](path);
}

int main(int argc, char **argv){
	PathFinder test((std::string(argv[1])), (std::string(argv[2])));
	test.SaveIt();
	return 0;
}