2.Sneaking

import java.util.Scanner;

public class Sneaking {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numberOfRows = Integer.parseInt(scanner.nextLine());

        String[][] matrix = new String[numberOfRows][numberOfRows*2];

        for (int i = 0; i < numberOfRows; i++) {
            String[] arr = scanner.nextLine().split("");

            matrix[i] = arr;
        }
        int xS = 0;
        int yS = 0;
        int xN = 0;
        int yN = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j].equals("N")) {
                    xN = i;
                    yN = j;
                }
                if (matrix[i][j].equals("S")) {
                    xS = i;
                    yS = j;
                }
            }
        }

        String[] movementOfSam = scanner.nextLine().split("");
        System.out.println();


        for (int i = 0; i < movementOfSam.length; i++) {

            switch (movementOfSam[i]) {
                case "U":
                    if (isPositionX(matrix)) {
                        System.out.println(String.format("Sam died at %d, %d", xS, yS));
                        printMatrix(matrix);
                        return;
                    }
                        movementOfEnemies(matrix, xS, yS);

                        checkWhoIsKilled(matrix, xS, yS);
                        for (int r = 1; r < matrix.length; r++) {
                            for (int c = 0; c < matrix[r].length; c++) {

                                if (matrix[r][c].equals("S")) {
                                    matrix[r - 1][c] = "S";
                                    matrix[r][c] = ".";
                                    xS = r - 1;
                                    yS = c;
                                }
                            }
                        }
                        if (xS == xN) {
                            matrix[xN][yN] = "X";

                            System.out.println("Nikoladze killed!");
                            printMatrix(matrix);
                            return;
                        }

                    break;

                case "D":
                    if (isPositionX(matrix)) {
                        System.out.println(String.format("Sam died at %d, %d", xS, yS));
                        printMatrix(matrix);
                        return;
                    }else {
                        movementOfEnemies(matrix, xS, yS);
                    }

                    checkWhoIsKilled(matrix, xS, yS);

                    for (int p = matrix.length - 1; p > 0; p--) {
                        for (int q = 0; q < matrix[p].length; q++) {

                            if (matrix[p][q].equals("S")) {
                                matrix[p + 1][q] = "S";
                                matrix[p][q] = ".";
                                xS = p + 1;
                                yS = q;

                            }
                        }
                    }
                    if (xS == xN) {
                        matrix[xN][yN] = "X";

                        System.out.println("Nikoladze killed!");
                        printMatrix(matrix);
                        return;
                    }

                    break;
                case "R":
                    if (isPositionX(matrix)) {
                        System.out.println(String.format("Sam died at %d, %d", xS, yS));
                        printMatrix(matrix);
                        return;
                    }else {
                        movementOfEnemies(matrix, xS, yS);
                    }

                    checkWhoIsKilled(matrix, xS, yS);
                    for (int r = 0; r < matrix.length; r++) {
                        for (int c = matrix[r].length - 1; c > 0; c--) {

                            if (matrix[r][c].equals("S")) {
                                matrix[r][c + 1] = "S";
                                matrix[r][c] = ".";
                                xS = r;
                                yS = c + 1;

                            }
                        }
                    }
                    if (xS == xN) {
                        matrix[xN][yN] = "X";

                        System.out.println("Nikoladze killed!");
                        printMatrix(matrix);
                        return;
                    }
                    break;
                case "L":
                    if (isPositionX(matrix)) {
                        System.out.println(String.format("Sam died at %d, %d", xS, yS));
                        printMatrix(matrix);
                        return;
                    }else {
                        movementOfEnemies(matrix, xS, yS);
                    }

                    checkWhoIsKilled(matrix, xS, yS);
                    for (int r = 0; r < matrix.length; r++) {
                        for (int c = 1; c < matrix[r].length; c++) {

                            if (matrix[r][c].equals("S")) {
                                matrix[r][c - 1] = "S";
                                matrix[r][c] = ".";
                                xS = r;
                                yS = c - 1;
                            }
                        }
                    }

                    if (xS == xN) {
                        matrix[xN][yN] = "X";

                        System.out.println("Nikoladze killed!");
                        printMatrix(matrix);
                        return;
                    }
                    break;
                case "W":
                    movementOfEnemies(matrix, xS, yS);
                    break;
            }
        }

    }

    public static String[][] movementOfEnemies(String[][] matrix, int x, int y) {

        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[r].length - 1; c++) {
                if (matrix[r][c].equals("b")) {
                    if (c == matrix[r].length - 1) {
                        matrix[r][c] = "d";

                    } else {
                        matrix[r][c] = ".";
                        matrix[r][++c] = "b";
                    }
                }
                if (matrix[r][c].equals("d")) {
                    if (c == 0) {
                        matrix[r][c] = "b";

                    }else {

                        matrix[r][c] = ".";
                        matrix[r][c - 1] = "d";
                    }
                }
            }
        }

        return matrix;
    }

    public static boolean checkWhoIsKilled(String[][] matrix, int x, int y) {
        for (int j = 0; j < matrix.length; j++) {
            for (int k = 0; k < matrix[j].length; k++) {
                if (matrix[j][k].equals("b") && x == j && y > k) {

                    matrix[x][y] = "X";

                    return false;
                } else if (matrix[j][k].equals("d") && x == j && y < k) {

                    matrix[x][y] = "X";

                    return false;
                }
            }
        }
        return true;
    }

    public static void printMatrix(String[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int l = 0; l < matrix[i].length; l++) {
                System.out.print(matrix[i][l]);
            }
            System.out.println();
        }
    }

    public static boolean isPositionX(String[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j].equals("X")) {
                    return true;
                }
            }
        }

        return false;
    }
}