// box.cpp 0.6
// author: elephant <elephant_AT_linux.net.cn>

#include <stdlib.h>
#include <stdio.h>

#include "solve.cpp"

#define HASH_SIZE (1024 * 1024 * 2)

#define MAX_BOXES_NUMBER 10
#define MAX_MAP_SIZE 64

class Box
{
	short human;
	short boxes[MAX_BOXES_NUMBER];
	// unsigned char human;
	// unsigned char boxes[MAX_BOXES_NUMBER];
public:
	int from;
	Box(short hu = 0, short *bs = 0);
	int possibleMoves() const;
	int move(int sw);
	int h() const;
	int isTarget() const;
	int isNull() const;
	int hash() const;
	friend int operator == (const Box &left, const Box &right);
	void output() const;
private:
	void findWay();
};

int number;
int mapSizeX, mapSizeY, mapArea;
int *map = 0;
int *way = 0;
int *dead_positions = 0;
Box box_push_directions;
int push_directions[MAX_BOXES_NUMBER];

Box::Box(short hu, short *bs)
{
	human = hu;
	if (hu)
	{
		int i;
		for (i = 0; i < number; i ++) boxes[i] = bs[i];
		findWay();
		for (i = 0; ; i ++) if (way[i] >= 0) break;
		human = i;
	}
}

int Box::possibleMoves() const
{
	return number << 2;
}

int Box::move(int sw)
{
	int i;
	int n = sw >> 2;
	int dir = sw & 0x3;

	if (!(box_push_directions == *this))
	{
		findWay();
		for (i = 0; i < number; i ++)
		{
			push_directions[i] = (way[boxes[i] - 1] >= 0);
			if (way[boxes[i] - mapSizeX] >= 0) push_directions[i] |= 2;
			if (way[boxes[i] + 1] >= 0) push_directions[i] |= 4;
			if (way[boxes[i] + mapSizeX] >= 0) push_directions[i] |= 8;
		}
		box_push_directions = *this;
	}

	int pushTo = boxes[n];
	int standOn = boxes[n];
	
	if (dir == 0) { pushTo ++; standOn --; }
	else if (dir == 1) { pushTo += mapSizeX; standOn -= mapSizeX; }
	else if (dir == 2) { pushTo --; standOn ++; }
	else { pushTo -= mapSizeX; standOn += mapSizeX; }

	if (!(push_directions[n] & (1 << dir))) return MOVE_NOWAY;
	else if (map[pushTo] < 0) return MOVE_NOWAY;
	else if (dead_positions[pushTo] & 1) return MOVE_NOWAY;
	for (i = 0; i < number; i ++)
	{
		if (boxes[i] == pushTo) return MOVE_NOWAY;
		if (i == n) continue;
		else if (boxes[i] == pushTo - 1) { if (dead_positions[boxes[i]] & 2) return MOVE_NOWAY; }
		else if (boxes[i] == pushTo + 1) { if (dead_positions[pushTo] & 2) return MOVE_NOWAY; }
		else if (boxes[i] == pushTo - mapSizeX) { if (dead_positions[boxes[i]] & 4) return MOVE_NOWAY; }
		else if (boxes[i] == pushTo + mapSizeX) { if (dead_positions[pushTo] & 4) return MOVE_NOWAY; }
	}

	boxes[n] = pushTo;
	human = standOn;

	if (dir == 1)
	{
		for (i = n; i < number - 1; i ++)
			if (boxes[i] > boxes[i + 1])
			{
				int swap = boxes[i];
				boxes[i] = boxes[i + 1];
				boxes[i + 1] = swap;
			}
			else break;
	}
	else if (dir == 3)
	{
		for (i = n - 1; i >= 0; i --)
			if (boxes[i] > boxes[i + 1])
			{
				int swap = boxes[i];
				boxes[i] = boxes[i + 1];
				boxes[i + 1] = swap;
			}
			else break;
	}

	findWay();
	for (i = 0; ; i ++) if (way[i] >= 0) break;
	human = i;

	return 0;
}

int Box::h() const
{
	int value = 0;
	for (int i = 0; i < number; i ++) value += map[boxes[i]] << 1;
		// '<< 1' for faster but not optimum solution
	return value;
}

int Box::isTarget() const
{
	for (int i = 0; i < number; i ++) if (map[boxes[i]]) return false;
	return true;
}

int Box::isNull() const
{
	return human == 0;
}

int Box::hash() const
{
	long long a = human;
	int shift = (24 + number) / number;
	for (int i = 0; i < number; i ++) a = (a << shift) + boxes[i];
	return a * a >> 16;
}

int operator == (const Box &left, const Box &right)
{
	if (left.human != right.human) return false;
	else if (left.human == 0) return true;
	for (int i = 0; i < number; i ++)
		if (left.boxes[i] != right.boxes[i]) return false;
	return true;
}

void Box::output() const
{
	char *out = new char[mapArea];
	int i;

	for (i = 0; i < mapArea; i ++)
		if (map[i] == -1) out[i] = '#';
		else if (map[i] == 0) out[i] = '.';
		else out[i] = ' ';
	for (i = 0; i < number; i ++)
		if (out[boxes[i]] == '.') out[boxes[i]] = '*';
		else out[boxes[i]] = '$';
	if (out[human] == '.') out[human] = '+';
	else out[human] = '@';

	for (i = 0; i < mapArea; i ++)
	{
		printf("%c", out[i]);
		if (i % mapSizeX == mapSizeX - 1) printf("\n");
	}

	delete []out;
}

void Box::findWay()
{
	int i;
	for (i = 0; i < mapArea; i ++) way[i] = (map[i] < 0) ? -1 : -2;
	for (i = 0; i < number; i ++) way[boxes[i]] = -1;
	way[human] = 0;

	int p = 0, top = 1;
	int queue[MAX_MAP_SIZE * MAX_MAP_SIZE];
	queue[0] = human;

	while (p < top)
	{
		int cur = queue[p];
		if (way[cur + 1] == -2)
		{
			way[cur + 1] = 0;
			queue[top] = cur + 1;
			top ++;
		}
		if (way[cur + mapSizeX] == -2)
		{
			way[cur + mapSizeX] = 0;
			queue[top] = cur + mapSizeX;
			top ++;
		}
		if (way[cur - 1] == -2)
		{
			way[cur - 1] = 0;
			queue[top] = cur - 1;
			top ++;
		}
		if (way[cur - mapSizeX] == -2)
		{
			way[cur - mapSizeX] = 0;
			queue[top] = cur - mapSizeX;
			top ++;
		}
		p ++;
	}
}

Box readBox()
{
	char tmp[MAX_MAP_SIZE][MAX_MAP_SIZE];
	mapSizeX = 0;
	mapSizeY = 0;
	while (fgets(tmp[mapSizeY], MAX_MAP_SIZE - 1, stdin))
	{
		int len = 0;
		while (tmp[mapSizeY][len] >= ' ') len ++;
		if (len > mapSizeX) mapSizeX = len;
		else if (len == 0) break;
		mapSizeY ++;
	}
	mapArea = mapSizeX * mapSizeY;

	if (mapArea == 0) return Box(0, 0);

	map = new int[mapArea];
	way = new int[mapArea];
	short hu;
	short bs[MAX_BOXES_NUMBER];
	int n = 0;
	int queue[MAX_MAP_SIZE * MAX_MAP_SIZE];
	int p = 0, top = 0;

	int i, j;
	for (i = 0; i < mapArea; i ++) map[i] = -2;
	for (i = 0; i < mapArea; i ++)
	{
		char t = tmp[i / mapSizeX][i % mapSizeX];
		if (t < ' ') { i = (i / mapSizeX + 1) * mapSizeX - 1; continue; }
		if (t == '#') map[i] = -1;
		else if (t == '.') { map[i] = 0; queue[top] = i; top ++; }
		else if (t == '*')
		{
			map[i] = 0; queue[top] = i; top ++;
			if (n >= MAX_BOXES_NUMBER)
			{
				printf("too more boxes\n");
				return Box();
			}
			bs[n] = i; n ++;
		}
		else if (t == '$')
		{
			if (n >= MAX_BOXES_NUMBER)
			{
				printf("too more boxes\n");
				return Box();
			}
			bs[n] = i; n ++;
		}
		else if (t == '@') hu = i;
		else if (t == '+') { map[i] = 0; queue[top] = i; top ++; hu = i; }
	}

	while (p < top)
	{
		int cur = queue[p];
		if (map[cur + 1] == -2)
		{
			map[cur + 1] = map[cur] + 1;
			queue[top] = cur + 1;
			top ++;
		}
		if (map[cur + mapSizeX] == -2)
		{
			map[cur + mapSizeX] = map[cur] + 1;
			queue[top] = cur + mapSizeX;
			top ++;
		}
		if (map[cur - 1] == -2)
		{
			map[cur - 1] = map[cur] + 1;
			queue[top] = cur - 1;
			top ++;
		}
		if (map[cur - mapSizeX] == -2)
		{
			map[cur - mapSizeX] = map[cur] + 1;
			queue[top] = cur - mapSizeX;
			top ++;
		}
		p ++;
	}

	dead_positions = new int[mapArea];
	for (i = 0; i < mapArea; i ++) dead_positions[i] = 0;
	for (i = 0; i < mapSizeX; i ++)
		for (j = 0; j < mapSizeY; j ++)
		{
			if (map[i + j * mapSizeX] >= 0)
			{
				int k, length;
				int dead = false;
				for (length = 1; length <= mapSizeY; length ++)
					if (map[i + (j + length) * mapSizeX] < 0) break;
				for (k = 0; k < length; k ++) if (map[i + (j + k) * mapSizeX] == 0) break;
				if (k == length)
				{
					for (k = 0; k < length; k ++) if (map[i - 1 + (j + k) * mapSizeX] >= 0) break;
					if (k == length) dead = true;
					else
					{
						for (k = 0; k < length; k ++) if (map[i + 1 + (j + k) * mapSizeX] >= 0) break;
						if (k == length) dead = true;
					}
					if (dead)
						for (k = 0; k < length; k ++) dead_positions[i + (j + k) * mapSizeX] |= 1;
				}
				j += length;
			}
		}
	for (j = 0; j < mapSizeY; j ++)
		for (i = 0; i < mapSizeX; i ++)
		{
			if (map[i + j * mapSizeX] >= 0)
			{
				int k, length;
				int dead = false;
				for (length = 1; length <= mapSizeX; length ++)
					if (map[i + length + j * mapSizeX] < 0) break;
				for (k = 0; k < length; k ++) if (map[i + k + j * mapSizeX] == 0) break;
				if (k == length)
				{
					for (k = 0; k < length; k ++) if (map[i + k + (j - 1) * mapSizeX] >= 0) break;
					if (k == length) dead = true;
					else
					{
						for (k = 0; k < length; k ++) if (map[i + k + (j + 1) * mapSizeX] >= 0) break;
						if (k == length) dead = true;
					}
					if (dead)
						for (k = 0; k < length; k ++) dead_positions[i + k + j * mapSizeX] |= 1;
				}
				i += length;
			}
		}
	for (i = 0; i < mapArea; i ++)
	{
		if (map[i] <= 0 || (dead_positions[i] & 1)) continue;
		if ((map[i - 1] < 0 || map[i + 1] < 0) && (map[i - mapSizeX] < 0 || map[i + mapSizeX] < 0))
			dead_positions[i] |= 1;
	}
	for (i = 0; i < mapArea; i ++)
	{
		if (map[i] < 0) continue;
		if (map[i + 1] >= 0 && (map[i] != 0 || map[i + 1] != 0))
		{
			if ((map[i - mapSizeX] < 0 || map[i + mapSizeX] < 0)
				&& (map[i + 1 - mapSizeX] < 0 || map[i + 1 + mapSizeX] < 0))
				dead_positions[i] |= 2;
		}
		if (map[i + mapSizeX] >= 0 && (map[i] != 0 || map[i + mapSizeX] != 0))
		{
			if ((map[i - 1] < 0 || map[i + 1] < 0)
				&& (map[i + mapSizeX - 1] < 0 || map[i + mapSizeX + 1] < 0))
				dead_positions[i] |= 4;
		}
	}

	number = n;

	return Box(hu, bs);
}

int main(int argc, char **argv)
{
	Box *nodes = new Box[HASH_SIZE];

	Box s = readBox();
	if (s.isNull()) return 0;

	int t = solve(nodes, HASH_SIZE, s);

	if (t == SOLV_IMPOSSIBLE) printf("impossible\n");
	else if (t == SOLV_NOMEMORY) printf("out of memory\n");
	else
	{
		while (t >= 0)
		{
			nodes[t].output();
			printf("\n");
			t = nodes[t].from;
		}
	}

// debug code begin
	int c = 0, u = 0;
	for (int i = 0; i < HASH_SIZE; i ++)
	{
		if (!nodes[i].isNull())
		{
			u ++;
			if (abs(nodes[i].hash()) % HASH_SIZE != i) c ++;
		}
	}
	printf("hash used: %d\n", u);
	printf("collision: %d\n", c);
// debug code end

	if (map) delete []map;
	if (way) delete []way;
	if (dead_positions) delete []dead_positions;

	return 0;
}
// vim: ts=2 sw=2 fdm=marker