using System;

namespace matrixretakeexamadvanced
{
    class Program
    {
        static void Main(string[] args)
        {
            int marioLive = int.Parse(Console.ReadLine());
            int n = int.Parse(Console.ReadLine());

            char[,] matrix = new char[n, n];

            int marioOldRow = 0;
            int marioOldCol = 0;

            int marioNewRow = 0;
            int marioNewCol = 0;

            bool isWon = false;


            for (int rows = 0; rows < n; rows++)
            {
                var command = Console.ReadLine().ToCharArray();

                for (int cols = 0; cols < n; cols++)
                {
                    matrix[rows, cols] = command[cols];

                    if(matrix[rows, cols] == 'M')
                    {
                        marioNewRow = rows;
                        marioNewCol = cols;
                    }
                }
            }


            //down=(row++, col), up=(row--, col), right=(row, col++), left=(row, col--)

            matrix[marioNewRow, marioNewCol] = '-';


            while (true)
            {
                string[] command = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);

                marioOldRow = marioNewRow;
                marioOldCol = marioNewCol;

                string direction = command[0];
                int bowserRow = int.Parse(command[1]);
                int bowserCol = int.Parse(command[2]);

                matrix[bowserRow, bowserCol] = 'B';

                matrix[marioOldRow, marioOldCol] = '-';

                if(direction == "W")
                {
                    marioNewRow -= 1;
                }
                else if(direction == "S")
                {
                    marioNewRow += 1;
                }
                else if(direction == "A")
                {
                    marioNewCol -= 1;
                }
                else if(direction == "D")
                {
                    marioNewCol += 1;
                }
                marioLive -= 1;

                if(!IsValidCell(marioNewRow, marioNewCol, n))
                {
                    switch (direction)
                    {
                        case "D":
                            marioNewCol -= 1;
                            break;
                        case "W":
                            marioNewRow += 1;
                            break;
                        case "S":
                            marioNewRow -= 1;
                            break;
                        case "A":
                            marioNewCol += 1;
                            break;
                        default:
                            break;
                    }
                }

                if(matrix[marioNewRow, marioNewCol] == 'B')
                {
                    marioLive -= 2;
                }
                if (matrix[marioNewRow, marioNewCol] == 'P')
                {
                    matrix[marioNewRow, marioNewCol] = '-';
                    isWon = true;
                    break;
                }

                if (marioLive <= 0)
                {
                    matrix[marioNewRow, marioNewCol] = 'X';
                    break;
                }

                matrix[marioNewRow, marioNewCol] = 'M';
            }


            if (isWon)
            {
                Console.WriteLine($"Mario has successfully saved the princess! Lives left: {marioLive}");
            }
            else
            {
                Console.WriteLine($"Mario died at {marioNewRow};{marioNewCol}.");
            }

            for (int rows = 0; rows < n; rows++)
            {
                for (int cols = 0; cols < n; cols++)
                {
                    Console.Write(matrix[rows, cols]);
                }
                Console.WriteLine();
            }
        }

        private static bool IsValidCell(int row, int col, int n)
        {
            return row >= 0 && row < n && col >= 0 && col < n;

        }
    }
}