#include "validate.h"
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

const int MAX_STEPS = 100000;
const int MAX_AREA = 1000000;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *dname = "NESW";

bool is_trap(char c) { return c == 'A' || c == 'B'; }
bool is_endpoint(char c) { return c == 'a' || c == 'b'; }

vector<string> read_map(istream &in, feedback_function feedback) {
    int H, W;
	if (!(in >> H >> W))
		feedback("Cannot read map size and position\n");

    if (W <= 0 || H <= 0)
        feedback("Non-positive dimension(s) %d x %d\n", H, W);

    if (W > MAX_AREA || H > MAX_AREA || (long long)W*H > MAX_AREA)
        feedback("Too large map %d x %d\n", H, W);
    
    vector<string> Map(H);
    map<char, int> freqs;
    for (int r = 0; r < H; ++r) {
        if (!(in >> Map[r]))
            feedback("Cannot read row %d/%d of the map\n", r+1, H);
        if (Map[r].length() != W)
            feedback("Row %d/%d has wrong length %d expected %d\n", r+1, H, Map[r].length(), W);
        for (int c = 0; c < W; ++c) {
            if (!strchr(".#AaBbS", Map[r][c]))
                feedback("Row %d col %d invalid character ascii code %d\n",
                         r+1, c+1, Map[r][c]);
            ++freqs[Map[r][c]];
        }
    }
    if (freqs['S'] != 1)
        feedback("Map contains %d 'S', must be exactly 1\n", freqs['S']);
    for (char c: "AaBb") 
        if (freqs[c] > 1)
            feedback("Map contains %d '%c', must be at most 1\n", freqs[c], c);
    if (freqs['A'] != freqs['a'])
        feedback("Map contains %d 'A' and %d 'a', must be same counts\n", freqs['A'], freqs['a']);
    if (freqs['B'] != freqs['b'])
        feedback("Map contains %d 'B' and %d 'b', must be same counts\n", freqs['B'], freqs['b']);
    return Map;
}

string get_surroundings(const vector<string> &Map, int r, int c) {
    string msg(4, '.');
    for (int d = 0; d < 4; ++d)
        if (Map[r+dr[d]][c+dc[d]] == '#')
            msg[d] = '#';
    return msg;
}

typedef pair<int, int> pii;

vector<pair<pii, pii>> get_traps(const vector<string> &Map) {
    vector<pair<pii, pii>> res(2);
    for (int i = 0; i < 2; ++i)
        res[i] = make_pair(pii(-1, -1), pii(-1, -1));
    
    for (int r = 0; r < Map.size(); ++r)
        for (int c = 0; c < Map[0].size(); ++c) {
            if (is_trap(Map[r][c]))
                res[Map[r][c]-'A'].first = make_pair(r, c);
            else if (is_endpoint(Map[r][c]))
                res[Map[r][c]-'a'].second = make_pair(r, c);
        }
    sort(res.begin(), res.end());
    return res;
}

void compare_maps(const vector<string>& answer, const vector<string>& output) {
    int H = answer.size();
    int W = answer[0].size();
    if (output.size() != H || output[0].size() != W)
        wrong_answer("Solution output map of wrong dimensions %d x %d, expected %d x %d\n",
                     output.size(), output[0].size(), H, W);

    auto answer_traps = get_traps(answer);
    auto output_traps = get_traps(output);
    if (answer_traps != output_traps)
        wrong_answer("Trap positions wrong:\n answer has (%d,%d) -> (%d,%d) and (%d,%d) -> (%d,%d)\n output has (%d,%d) -> (%d,%d) and (%d,%d) -> (%d, %d)\n",
                     answer_traps[0].first.first, answer_traps[0].first.second,
                     answer_traps[0].second.first, answer_traps[0].second.second,
                     answer_traps[1].first.first, answer_traps[1].first.second,
                     answer_traps[1].second.first, answer_traps[1].second.second,
                     output_traps[0].first.first, output_traps[0].first.second,
                     output_traps[0].second.first, output_traps[0].second.second,
                     output_traps[1].first.first, output_traps[1].first.second,
                     output_traps[1].second.first, output_traps[1].second.second);
    
    for (int r = 0; r < H; ++r)
        for (int c = 0; c < W; ++c) {
            if (is_trap(answer[r][c]) || is_endpoint(answer[r][c])) continue;
            if (answer[r][c] != output[r][c])
                wrong_answer("Error in map at position (%d,%d), expected '%c' got '%c'\n",
                             r, c, answer[r][c], output[r][c]);
        }
}

void run() {
    auto Map = read_map(judge_in, judge_error);
    pii endpoints[2];
    
    int r, c;
    for (int i = 0; i < Map.size(); ++i)
        for (int j = 0; j < Map[i].size(); ++j)
            if (Map[i][j] == 'S') {
                r = i;
                c = j;
            } else if (is_endpoint(Map[i][j])) {
                endpoints[Map[i][j]-'a'] = make_pair(i, j);
            }

    int steps = 0;
    while (true) {
        cout << get_surroundings(Map, r, c);
        if (is_trap(Map[r][c])) {
            cout << " trap ";
            auto [nr, nc] = endpoints[Map[r][c]-'A'];
            r = nr;
            c = nc;
            cout << get_surroundings(Map, r, c);
        } else {
            cout << " ok";
        }
        cout << endl;

        string action;
        author_out >> action;
        if (action == "done")
            break;

        if (action.length() != 1 || !strchr(dname, action[0]))
            wrong_answer("Invalid action '%s'\n", action.c_str());

        if (++steps > MAX_STEPS) {
            wrong_answer("Step count limit of %d exceeded\n", MAX_STEPS);
        }

        int d = strchr(dname, action[0]) - dname;
        r += dr[d];
        c += dc[d];
        if (Map[r][c] == '#')
            wrong_answer("Walked into a wall at position (%d,%d)\n", r, c);
    }

    auto output = read_map(author_out, wrong_answer);
    compare_maps(Map, output);
}


int main(int argc, char* argv[]) {
	init_io(argc, argv);

    run();
	
	string excess;
	if (author_out >> excess) {
		wrong_answer("Trailing output after solving\n");
	}
	
	accept();
}