#include <iostream>
#include <string>
#include <utility>
#include <vector>

struct position {
	int row;
	int col;
};
using ogre_map = std::vector<std::string>;

ogre_map sample_maps[] = {
	{ // Example input 1
		"@@........",
		"@@O.......",
		".....O.O..",
		"..........",
		"..O.O.....",
		"..O....O.O",
		".O........",
		"..........",
		".....OO...",
		".........$"
	},
	{ // Example input 2
		"@@........",
		"@@O.......",
		".....O.O..",
		"..........",
		"..O.O.....",
		"..O....O.O",
		".O........",
		"..........",
		".....OO.O.",
		".........$"
	},
	{ // Challenge input 1
		"$.O...O...",
		"...O......",
		"..........",
		"O..O..O...",
		"..........",
		"O..O..O...",
		"..........",
		"......OO..",
		"O..O....@@",
		"........@@"
	},
	{ // Challenge input 2
		".@@.....O.",
		".@@.......",
		"..O..O....",
		".......O..",
		"...O......",
		"..........",
		".......O.O",
		"...O.O....",
		".......O..",
		".........$"
	}
};

bool dfs(ogre_map& map, position pos) {
	char old = map[pos.row][pos.col];
	auto check_for = [&](char ch) {
		return old == ch || map[pos.row][pos.col+1] == ch ||
		       map[pos.row+1][pos.col] == ch || map[pos.row+1][pos.col+1] == ch;
	};
	if (old == '&' || check_for('O'))
	    return false; // already been there, or can't go there
	    
	map[pos.row][pos.col] = '&';
	if (check_for('$'))
	    return true; // we found it!
	    
	// recurse
	if (pos.row > 0 && dfs(map, {pos.row-1, pos.col})) // up
		return true;
	if (pos.col > 0 && dfs(map, {pos.row, pos.col-1})) // left
		return true;
	if (pos.row < map.size()-2 && dfs(map, {pos.row+1, pos.col})) // down
		return true;
	if (pos.col < map[0].size()-2 && dfs(map, {pos.row, pos.col+1})) // right
		return true;
	
	// not found
	map[pos.row][pos.col] = old;
	return false;
}

void biggify(ogre_map& map) {
	for (int r = map.size() - 1; r >= 0; --r)
		for (int c = map[0].size() - 1; c >= 1; --c)
			if ((r > 0 && (map[r-1][c-1] == '&' || map[r-1][c] == '&')) || map[r][c-1] == '&')
				map[r][c] = '&';
}

position find_start(const ogre_map& map) {
	for (int r = 0; r < map.size(); ++r)
		for (int c = 0; c < map[0].size(); ++c)
			if (map[r][c] == '@') return {r, c};
	return {-1, -1};
}

int main() {
	auto& input = sample_maps[2];
	
	position ogre_start = find_start(input);
	if (ogre_start.row < 0 || ogre_start.col < 0) {
		std::cout << "Is this a joke? You didn't put an ogre anywhere on the map!\n";
		std::exit(1);
	}
		
	if (dfs(input, ogre_start)) {
		biggify(input);
		for (auto& row : input) {
			std::cout << row << '\n';
		}
	} else {
		std::cout << "No Path\n";
	}
	return 0;
}