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

void print_position(int x, int y);

void print_maze(char **maze, int largura, int altura);

int labirinto(int x_atual, int y_atual, char **maze, int largura, int altura) {
    // Se tentou sair do labirinto, este não é o caminho certo.
    if (x_atual < 0 || x_atual >= largura || y_atual < 0 || y_atual >= altura) return 0;

    char aqui = maze[x_atual][y_atual];

    // Verifica se achou a saída.
    if (aqui == 'S') return 1;

    // Se bateu na parede ou voltou para algum lugar que já esteve,
    // então este não é o caminho certo.
    if (aqui == 'X' || aqui == '>' || aqui == '<' || aqui == 'v' || aqui == '^') return 0;

    // Tenta ir para cima.
    maze[x_atual][y_atual] = '^';
    if (labirinto(x_atual, y_atual + 1, maze, largura, altura)) return 1;

    // Tenta ir para baixo.
    maze[x_atual][y_atual] = 'v';
    if (labirinto(x_atual, y_atual - 1, maze, largura, altura)) return 1;

    // Tenta ir para a esquerda.
    maze[x_atual][y_atual] = '<';
    if (labirinto(x_atual - 1, y_atual, maze, largura, altura)) return 1;

    // Tenta ir para a direita.
    maze[x_atual][y_atual] = '>';
    if (labirinto(x_atual + 1, y_atual, maze, largura, altura)) return 1;

    // Não deu, então volta.
    maze[x_atual][y_atual] = 'O';   
    return 0;
}

int main(void) {
    int largura, altura, x_entrada, y_entrada;
    scanf("%d %d\n", &largura, &altura);
    char **a = malloc(largura * sizeof(char*));
    for (int x = 0; x < largura; x++) {
        a[x] = malloc(altura * sizeof(char));
    }
    for (int y = altura - 1; y >= 0; y--) {
        for (int x = 0; x < largura; x++) {
            a[x][y] = getchar();
            if (a[x][y] == 'E') {
                x_entrada = x;
                y_entrada = y;
            }
        }
        getchar(); //pegar a quebra de linha
    }
    printf("Entrada:\n");
    print_maze(a, largura, altura);
    labirinto(x_entrada, y_entrada, a, largura, altura);
    printf("\nSaída:\n");
    print_maze(a, largura, altura);
    return 0;
}

void print_maze(char **maze, int largura, int altura) {
    int x, y;
    for (y = altura - 1; y >= 0; y--) {
        for (x = 0; x < largura; x++) {
            printf("%c", maze[x][y]);
        }
        printf("\n");
    }
}

void print_position(int x, int y) {
    printf("(%d, %d)", x, y);
}