// Medvědovo řešení úlohy 32-5-3 (Bomberman uklízí efektivně)
// Vstup a výstup jsou kompatibilní s open-datovkou 32-Z4-4.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>

/*** Reprezentace mapy ***/

#define MAXDIM 260

typedef struct { int r, c; } pair;

// Mapa, její rozměry a počáteční políčko
char maze[MAXDIM][MAXDIM+1];
int R, C;
pair x0;

// Kódování políček
pair pos(int r, int c)
{
	return (pair) { r, c };
}

// Jsou dvě políčka stejná?
bool pair_eq(pair p, pair q)
{
	return p.r == q.r && p.c == q.c;
}

// Zjistí obsah políčka, mimo mapu domýšlí zdi
int get(pair p)
{
	if (p.r >= 0 && p.r < R && p.c >= 0 && p.c < C)
		return maze[p.r][p.c];
	else
		return '#';
}

// Je dané políčko volné (tj. ani zeď, ani trosky)?
bool is_free(pair p)
{
	int ch = get(p);
	return ch != '#' && ch != '*';
}

// Zápis do mapy. Na místa, kde už jsme byli, budeme pokládat "o".
void put(pair p, int x)
{
	maze[p.r][p.c] = x;
}

void read_input(FILE *f)
{
	fscanf(f, "%d%d", &R, &C);
	assert(R >= 1 && R <= MAXDIM);
	assert(C >= 1 && C <= MAXDIM);
	if (fgetc(f) != '\n')
		assert(0);

	x0 = pos(-1, -1);
	for (int r=0; r<R; r++) {
		for (int c=0; c<C; c++) {
			int x = fgetc(f);
			assert(x == '.' || x == '#' || x == '*' || x == 'P');
			if (x == 'P') {
				assert(x0.r < 0);
				x0 = pos(r, c);
				x = '.';
			}
			maze[r][c] = x;
		}
		maze[r][C] = 0;
		if (fgetc(f) != '\n')
			assert(0);
	}

	if (fgetc(f) >= 0)
		assert(0);
	assert(x0.r >= 0);
}

/*** Reprezentace směrů ***/

struct dir {
	int dr, dc;	// Posun
	int cmd;	// Odpovídající příkaz
};

// Směry jsou očíslovány tak, že pro směr d je d^1 ten opačný a d^2 jeden z kolmých
const struct dir dirs[4] = {
	{ +1,  0, 'D' },
	{ -1,  0, 'N' },
	{  0, +1, 'P' },
	{  0, -1, 'L' },
};

// Sousední políčko v daném směru
pair move(pair p, int d)
{
	return pos(p.r + dirs[d].dr, p.c + dirs[d].dc);
}

/*** Výstup ***/

/*
 *  Výslednou posloupnost příkazů si pamatujeme a kdykoliv se snažíme přidat
 *  příkaz inverzní k tomu předchozímu, anihilují se. Tím pádem se ve výstupu
 *  neobjeví prohledávání částí bludíště, ve kterých nejsou žádné trosky.
 *  Asymptoticky to nicméně nemá na velikost výstupu vliv.
 */

// Zásobník příkazů
#define OUTMAX (8*MAXDIM*MAXDIM)
char out_stack[OUTMAX];
int out_sp;

// Udržujeme aktuální pozici, ale používá se jen v assertech
pair curr;

void out_init(pair x0)
{
	curr = x0;
}

// Uloží příkaz
void out(int cmd)
{
	assert(out_sp < OUTMAX);
	out_stack[out_sp++] = cmd;
}

// Vypíše zásobník do výstupu
void out_flush(void)
{
	for (int i=0; i<out_sp; i++)
		putchar(out_stack[i]);
	putchar('\n');
}

// Uloží příkaz pro pohyb v daném směru
void out_dir(int d)
{
	curr = move(curr, d);
	assert(curr.r >= 0 && curr.r < R && curr.c >= 0 && curr.c < C);
	if (out_sp > 0 && out_stack[out_sp-1] == dirs[d^1].cmd) {
		out_sp--;
		return;
	}
	out(dirs[d].cmd);
}

/*** Hlavní DFS ***/

// Najde směr kolmý na d, ve kterém s políčkem p sousedí volné políčko (úkryt)
int shelter_dir(pair p, int d)
{
	for (int x=2; x<4; x++)
		if (is_free(move(p, d^x)))
			return d^x;
	assert(0);
}

void dfs(pair p, int d)
{
	/*
	 *  Invariant:
	 *
	 *     - od políčka p chci hledat ve směrech d a d^1.
	 *     - v aspoň jednom z těchto směrů je sousední políčko prázdné.
	 *     - v aspoň jednom z kolmých směrů je sousední políčko prázdné.
	 *     - o prohledání kolmých směrů se postará ten, kdo mě zavolal.
	 */

	// Aktuální políčko označíme za navštívené
	put(p, 'o');

	// bd je směr k volnému sousednímu políčku (B na obrázku)
	int bd = d;
	if (!is_free(move(p, bd))) {
		bd ^= 1;
		assert(is_free(move(p, bd)));
	}

	// ud je směr k úkrytu (U na obrázku)
	int ud = shelter_dir(p, d);

	// První průchod: vystřílíme všechny trosku v obou směrech hledání
	for (int i=0; i<2; i++) {
		pair pp = p;
		while (get(pp) != '#') {
			if (get(pp) == '*') {
				// Taneček: položíme bombu, zalezeme do úkrytu, odpálíme, vylezeme
				out_dir(bd);
				out('B');
				out_dir(bd^1);
				out_dir(ud);
				out('O');
				put(pp, '.');	// Výbuch nesimulujeme celý, ale aspoň tyto trosky zmizely
				out_dir(ud^1);
			}
			pp = move(pp, d);
		}
		d ^= 1;
	}
	assert(pair_eq(curr, p));

	// Druhý průchod: jdeme chodbou, hledáme odbočky (jsou-li v nich trosky, odpalujeme),
	// průběžně si udržujeme nejblížší úkryt. Každá další objevená odbočka se stane úkrytem
	// pro odpalování u další odbočky.
	for (int i=0; i<2; i++) {
		pair u = p;		// Sousedem tohoto políčka je úkryt
		pair pp = p;
		int dist=0;		// Kolik jsme ušli
		int udist = 0;		// a kolik z toho je od políčka u
		for (;;) {
			pp = move(pp, d);
			if (!is_free(pp))
				break;
			put(pp, 'o');
			out_dir(d);
			assert(pair_eq(curr, pp));
			dist++;
			udist++;

			// Pokud jsou v některém z kolmých směrů trosky, odpálíme je
			for (int x=2; x<4; x++) {
				pair r = move(pp, d^x);
				if (get(r) == '*') {
					// Položíme bombu a odejdeme do úkrytu
					out('B');
					for (int q=0; q<udist; q++)
						out_dir(d^1);
					ud = shelter_dir(u, d);
					out_dir(ud);

					// Odpálíme a vrátíme se zpátky
					out('O');
					put(r, '.');
					out_dir(ud^1);
					for (int q=0; q<udist; q++)
						out_dir(d);
					assert(pair_eq(curr, pp));
				}
			}

			// Pokud je v kolmém směru odbočka, zavoláme se rekurzivně
			// a navíc máme další úkryt pro náš směr.
			bool found_branch = false;
			for (int x=2; x<4; x++) {
				pair r = move(pp, d^x);
				if (get(r) == '.')
					found_branch = true;
			}
			if (found_branch) {
				dfs(pp, d^2);
				u = pp, udist = 0;
			}
		}

		// Nakonec se potřebujeme vrátit zpátky
		while (dist--)
			out_dir(d^1);

		// Příští iterace cyklu půjde opačným směrem
		d ^= 1;
	}
	assert(pair_eq(curr, p));
}

/*** Zahřívací DFS ***/

bool solve(pair p)
{
	/*
	 *  Na spuštění hlavního algoritmu je potřeba, aby platil invariant.
	 *  Proto nejdřív pomocí DFS prohledáme dosažitelnou oblast a hledáme
	 *  trojici volných políček ve tvaru "L". Pokud ji najdeme, odstartujeme
	 *  odtamtud hlavní algoritmus. V opačném případě má dosažitelná oblast
	 *  tvar jedné cesty, takže trosky (jsou-li) není možné odstranit.
	 */
	put(p, 'o');

	// Hledáme "L" s aktuálním políčkem uprostřed
	for (int d=0; d<4; d++) {
		if (is_free(move(p, d))) {
			for (int x=2; x<4; x++) {
				int dd = d ^ x;
				if (is_free(move(p, dd))) {
					// Nalezeno. Všechna zatím navštívená políčka prohlásíme za volná a spustíme hlavní DFS
					for (int r=0; r<R; r++)
						for (int c=0; c<R; c++)
							if (maze[r][c] == 'o')
								maze[r][c] = '.';
					dfs(p, d);

					// Jenže pozor, v kolmém směru mohou zbývat trosky, takže hlavní
					// DFS spustíme podruhé o 90° otočeně.
					dfs(p, dd);

					return true;
				}
			}
		}
	}

	// Pokračujeme v zahřívacím DFS
	for (int d=0; d<4; d++) {
		pair pp = move(p, d);
		if (get(pp) == '.') {
			out_dir(d);
			if (solve(pp))
				return true;
			out_dir(d^1);
		}
	}

	assert(pair_eq(curr, p));
	return false;
}

/*** Hlavní program ***/

int main(void)
{
	read_input(stdin);
	out_init(x0);
	solve(x0);
	out_flush();
	return 0;
}