MM98

solution.cpp

// C++11
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <random>

using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)

const unsigned long long int cycle_per_sec = 2500000000;

unsigned long long int getCycle() {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

double getTime (unsigned long long int begin_cycle) {
    return (double)(getCycle() - begin_cycle) / cycle_per_sec;
}

class XorShift {
public:
    unsigned int x;
    unsigned int y;
    unsigned int z;
    unsigned int w;
    unsigned int t;
    
    XorShift(int tmp) {
        mt19937 rnd(tmp);
        x = rnd();
        y = rnd();
        z = rnd();
        w = rnd();
        t = 1;
    }
    
    int rand() {
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
        return w & 0x7fffffff;
    }
} engine(rand());

const int INF = 100000;
const int dy[5] = {-1, 0, 1, 0, 0};
const int dx[5] = {0, 1, 0, -1, 0};
const int mainG = 8;
const int MAX_S = 50;
const int MAX_K = 100;
const int MAX_P = 50;
const int MAX_M = 500;
const int MONTE_TIME1 = 5;
const int MONTE_TIME2 = 10;
const int rec_ex = 3;

XorShift best_engine(0);

class PrincessesAndMonsters {
public:
    
    int corner[4][2]; //topleft, topright, bottomright, bottomleft
    int rectangle[MAX_S][MAX_S];
    int rec_edge[4]; // top, right, bottom, left
    int S;
    int end_turn;
    string dir_str = "NESWO";
    int split;
    
    int G[2];
    int age[2];
    int rec_len[2];
    int rec_index[2]; // topleft, topright, bottomright, bottomleft
    int rec_dir[2][2];
    bool age_first_day[2];
    int K[2];
    int Gindex[2][MAX_K];
    int Gsize[2];
    int Gknights[2][MAX_K*2];
    int Gdir[2][MAX_K];
    int knights[2][MAX_K*2];
    bool last_south[2];
    bool last_east[2];
    bool last_phase[2];
    
    int turn;
    
    inline int distance (int &y, int &x, int &Y, int &X) {
        return (x-X)*(x-X<0?-1:1)+(y-Y)*(y-Y<0?-1:1);
    }
    
    inline bool in_rectangle (int &y, int &x) {
        return rec_edge[0] <= y && y <= rec_edge[2] && rec_edge[3] <= x && x <= rec_edge[1];
    }
    
    inline bool in_board (int y, int x) {
        return 0 <= y && y < S && 0 <= x && x < S;
    } 
    
    void dynamic_init (vector<int> princesses, int ind, int KK, int _G, int pea) {
        G[0] = _G; G[1] = _G;
        if (ind == 0) {
            K[0] = KK;
            K[1] = 0;
        } else {
            K[0] = KK/2;
            K[1] = KK-KK/2;
        }
        turn = 0;
        age[0] = 0; age[1] = 0;
        rec_edge[0] = S-1; rec_edge[1] = 0; rec_edge[2] = 0; rec_edge[3] = S-1;
        for (int i = 0; i < princesses.size(); i += 2) {
            rec_edge[0] = min(rec_edge[0], princesses[i]);
            rec_edge[1] = max(rec_edge[1], princesses[i+1]);
            rec_edge[2] = max(rec_edge[2], princesses[i]);
            rec_edge[3] = min(rec_edge[3], princesses[i+1]);
        }
        rec_edge[0] = max(1, rec_edge[0]-rec_ex);
        rec_edge[1] = min(S-2, rec_edge[1]+rec_ex);
        rec_edge[2] = min(S-2, rec_edge[2]+rec_ex);
        rec_edge[3] = max(1, rec_edge[3]-rec_ex);
        //cerr << "hoge" << endl;
        if (rec_edge[0] <= S-1-rec_edge[2]) {
            if (S-1-rec_edge[1] <= rec_edge[3]) rec_index[0] = 1;
            else rec_index[0] = 0;
        } else {
            if (S-1-rec_edge[1] <= rec_edge[3]) rec_index[0] = 2;
            else rec_index[0] = 3;
        }
        rec_index[1] = (rec_index[0]+pea)%4;
        rep(j,2) {
            rep(i,K[j]) {
                if (rec_index[j] <= 1) knights[j][2*i] = 0;
                else knights[j][2*i] = S-1;
                if (rec_index[j] == 1 || rec_index[j] == 2) knights[j][2*i+1] = S-1;
                else knights[j][2*i+1] = 0;
            }
            if (rec_index[j] == 0) {
                rec_dir[j][0] = 1; rec_dir[j][1] = 2;
            } else if (rec_index[j] == 1) {
                rec_dir[j][0] = 3; rec_dir[j][1] = 2;
            } else if (rec_index[j] == 2) {
                rec_dir[j][0] = 3; rec_dir[j][1] = 0;
            } else {
                rec_dir[j][0] = 1; rec_dir[j][1] = 0;
            }
        }
        //cerr << "huga" << endl;
        /*
        rep(i,K[0]) cerr << knights[0][2*i] << " " << knights[0][2*i+1] << " ";
        cerr << endl;
        rep(i,K[1]) cerr << knights[1][2*i] << " " << knights[1][2*i+1] << " ";
        cerr << endl;
        */
        //cerr << "?" << endl;
        rep(i,2) rec_len[i] = 1+rec_edge[2]-rec_edge[0]+rec_edge[1]-rec_edge[3];
        memset(rectangle, 0, sizeof(rectangle));
        
        rep(i,2) {
            last_south[i] = true;
            last_east[i] = true;
            last_phase[i] = false;
        }
    }
    
    pair<int,int> battle (int x, int y) {
        while (x != 0 && y != 0) {
            if (engine.rand()%(x+y) < x) y--;
            else x--;
        }
        return pair<int,int>(x,y);
    }
    
    // ----------------------------------------------
    string initialize (int SS, vector<int> princesses, vector<int> monsters, int KK) {
        S = SS; 
        corner[0][0] = 0; corner[0][1] = 0;
        corner[1][0] = 0; corner[1][1] = S-1;
        corner[2][0] = S-1; corner[2][1] = S-1;
        corner[3][0] = S-1; corner[3][1] = 0;
        end_turn = S*S*S;
        
        // ---
        // G..[2,4], rec_ex..[0,5]
        auto start = getCycle();
        int score[4][5];
        int monte = 0;
        int board[3][MAX_S][MAX_S];
        int last_dead[3][MAX_S][MAX_S];
        bool dead[3][MAX_M];
        int follow[MAX_P];
        int now_princesses[MAX_P*2], now_monsters[MAX_M*2];
        int now_knights[MAX_K*2];
        int P = princesses.size()/2, M = monsters.size()/2;
        int debug = 0;
        //cerr << "ok" << endl;
        vector<int> status;
        memset(score, 0, sizeof(score));
        while (getTime(start) < MONTE_TIME1) {
            //cerr << "monte" << endl;
            monte++;
            int xorrnd = engine.rand();
            for (int sp = 0; sp < 4; sp++) {
                for (int _G = 1; _G <= 3; _G++) {
                    XorShift tmp_engine(xorrnd);
                    dynamic_init(princesses, (int)(sp!=0), KK, _G, sp);
                    //cerr << "dy init" << endl;
                    status = vector<int>(KK, 0);
                    memset(dead, 0, sizeof(dead));
                    memset(follow, -1, sizeof(follow));
                    int nowP = princesses.size()/2, nowM = monsters.size()/2;
                    
                    for (int i = 0; i < 2*P; i++) now_princesses[i] = princesses[i];
                    for (int i = 0; i < 2*M; i++) now_monsters[i] = monsters[i];
                    //cerr << "ok1" << endl;
                    
                    for (int _ = 0; _ < 5*S; _++) {
                        //cerr << "ok2" << endl;
                        memset(board, 0, sizeof(board));
                        memset(last_dead, 0, sizeof(last_dead));
                        int tmpP = 0;
                        int tmpK = 0;
                        for (int i = 0; i < status.size(); i++) {
                            if (status[i] > 0) tmpP += status[i];
                            if (status[i] >= 0) tmpK++;
                        }
                        if (sp == 0) {
                            string tmp = split_move(status, nowP, nowM, INF, 0, tmpP, tmpK, engine);
                        } else {
                            string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), nowP, nowM, INF, 0, tmpP, tmpK, engine)
                                       + split_move(vector<int>(status.begin()+K[0], status.end()), nowP, nowM, INF, 1, tmpP, tmpK, engine);
                        }
                        if (sp == 0) {
                            for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i];
                        } else {
                            for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i];
                            for (int i = 0; i < 2*K[1]; i++) now_knights[2*K[0]+i] = knights[1][i];
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            board[0][now_knights[i*2]][now_knights[i*2+1]]++;
                        }
                        //cerr << "ok3" << endl;
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            if (follow[i] != -1) {
                                now_princesses[2*i] = now_knights[2*follow[i]];
                                now_princesses[2*i+1] = now_knights[2*follow[i]+1];
                            } else {
                                int r;
                                while (true) {
                                    r = tmp_engine.rand()%5;
                                    if (in_board(now_princesses[2*i]+dy[r], now_princesses[2*i+1]+dx[r])) break;
                                }
                                now_princesses[2*i] += dy[r];
                                now_princesses[2*i+1] += dx[r];
                            }
                            if (now_princesses[2*i] == 0) {
                                if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) {
                                    dead[1][i] = true;
                                    nowP--;
                                }
                            } else if (now_princesses[2*i] == S-1) {
                                if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) {
                                    dead[1][i] = true;
                                    nowP--;
                                }
                            }
                            if (!dead[1][i]) board[1][now_princesses[2*i]][now_princesses[2*i+1]]++;
                        }
                        //cerr << "ok4" << endl;
                        for (int i = 0; i < M; i++) {
                            if (dead[2][i]) continue;
                            int r;
                            while (true) {
                                r = tmp_engine.rand()%5;
                                if (in_board(now_monsters[2*i]+dy[r], now_monsters[2*i+1]+dx[r])) break;
                            }
                            now_monsters[2*i] += dy[r];
                            now_monsters[2*i+1] += dx[r];
                            board[2][now_monsters[2*i]][now_monsters[2*i+1]]++;
                        }
                        /*
                        if (debug < 10) {
                            debug++;
                            for (int i = 0; i < 3; i++) {
                                for (int j = 0; j < S; j++) {
                                    for (int k = 0; k < S; k++) {
                                        cerr << board[i][j][k] << " ";
                                    }
                                    cerr << endl;
                                }
                                cerr << endl;
                            }
                        }
                        */
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            int cntK = board[0][y][x];
                            int cntM = board[2][y][x];
                            if (cntK == 0 || cntM == 0) continue;
                            pair<int,int> result = battle(cntK, cntM);
                            
                            board[0][y][x] -= (cntK-result.first);
                            last_dead[0][y][x] = cntK-result.first;
                            board[2][y][x] -= (cntM-result.second);
                            last_dead[2][y][x] = cntM-result.second;
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            if (last_dead[0][y][x] > 0) {
                                dead[0][i] = true;
                                last_dead[0][y][x]--;
                                status[i] = -1;
                            }
                        }
                        //cerr << "ok5" << endl;
                        for (int i = 0; i < M; i++) {
                            if (dead[2][i]) continue;
                            int y = now_monsters[2*i], x = now_monsters[2*i+1];
                            if (last_dead[2][y][x] > 0) {
                                dead[2][i] = true;
                                last_dead[2][y][x]--;
                                nowM--;
                            }
                        }
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            int y = now_princesses[2*i], x = now_princesses[2*i+1];
                            if (board[2][y][x]) {
                                dead[1][i] = true;
                                board[1][y][x]--;
                                nowP--;
                            }
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            status[i] = 0;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            if (board[1][y][x]) {
                                status[i] = board[1][y][x];
                                board[1][y][x] = 0;
                                board[0][y][x] = i+1;
                            }
                        }
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            int y = now_princesses[2*i], x = now_princesses[2*i+1];
                            if (board[0][y][x] > 0) {
                                follow[i] = board[0][y][x]-1;
                            }
                        }
                        /*
                        if (debug < 50) {
                            debug++;
                            for (int ii = 0; ii < status.size(); ii++) {
                                cerr << status[ii] << " ";
                            }
                            cerr << endl;
                        }
                        */
                    }
                    int this_score = 0;
                    for (int i = 0; i < KK; i++) {
                        if (status[i] == -1) this_score -= 10;
                        if (status[i] > 0) this_score += status[i]*100;
                    }
                    score[sp][_G] += this_score;
                }
            }
        }
        //cerr << "monte " << monte << endl;
        int best_score = -INF;
        int _G;
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <= 3; j++) {
                //cerr << best_score << " ";
                if (score[i][j] > best_score) {
                    best_score = score[i][j];
                    split = i;
                    _G = j;
                }
            }
            //cerr << endl;
        }
        
        int rand_seed[4][5];
        rep(i,4) rep(j,5) rand_seed[i][j] = engine.rand();
        memset(score, 0, sizeof(score));
        while (getTime(start) < MONTE_TIME2) {
            //cerr << "monte" << endl;
            monte++;
            int xorrnd = engine.rand();
            for (int u = 0; u < 4; u++) {
                for (int v = 0; v < 5; v++) {
                    XorShift tmp_engine(xorrnd);
                    XorShift now_engine(rand_seed[u][v]);
                    dynamic_init(princesses, (int)(split!=0), KK, _G, split);
                    //cerr << "dy init" << endl;
                    status = vector<int>(KK, 0);
                    memset(dead, 0, sizeof(dead));
                    memset(follow, -1, sizeof(follow));
                    int nowP = princesses.size()/2, nowM = monsters.size()/2;
                    
                    for (int i = 0; i < 2*P; i++) now_princesses[i] = princesses[i];
                    for (int i = 0; i < 2*M; i++) now_monsters[i] = monsters[i];
                    //cerr << "ok1" << endl;
                    
                    for (int _ = 0; _ < 5*S; _++) {
                        //cerr << "ok2" << endl;
                        memset(board, 0, sizeof(board));
                        memset(last_dead, 0, sizeof(last_dead));
                        int tmpP = 0;
                        int tmpK = 0;
                        for (int i = 0; i < status.size(); i++) {
                            if (status[i] > 0) tmpP += status[i];
                            if (status[i] >= 0) tmpK++;
                        }
                        if (split == 0) {
                            string tmp = split_move(status, nowP, nowM, INF, 0, tmpP, tmpK, now_engine);
                        } else {
                            string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), nowP, nowM, INF, 0, tmpP, tmpK, now_engine)
                                       + split_move(vector<int>(status.begin()+K[0], status.end()), nowP, nowM, INF, 1, tmpP, tmpK, now_engine);
                        }
                        if (split == 0) {
                            for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i];
                        } else {
                            for (int i = 0; i < 2*K[0]; i++) now_knights[i] = knights[0][i];
                            for (int i = 0; i < 2*K[1]; i++) now_knights[2*K[0]+i] = knights[1][i];
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            board[0][now_knights[i*2]][now_knights[i*2+1]]++;
                        }
                        //cerr << "ok3" << endl;
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            if (follow[i] != -1) {
                                now_princesses[2*i] = now_knights[2*follow[i]];
                                now_princesses[2*i+1] = now_knights[2*follow[i]+1];
                            } else {
                                int r;
                                while (true) {
                                    r = tmp_engine.rand()%5;
                                    if (in_board(now_princesses[2*i]+dy[r], now_princesses[2*i+1]+dx[r])) break;
                                }
                                now_princesses[2*i] += dy[r];
                                now_princesses[2*i+1] += dx[r];
                            }
                            if (now_princesses[2*i] == 0) {
                                if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) {
                                    dead[1][i] = true;
                                    nowP--;
                                }
                            } else if (now_princesses[2*i] == S-1) {
                                if (now_princesses[2*i+1] == 0 || now_princesses[2*i+1] == S-1) {
                                    dead[1][i] = true;
                                    nowP--;
                                }
                            }
                            if (!dead[1][i]) board[1][now_princesses[2*i]][now_princesses[2*i+1]]++;
                        }
                        //cerr << "ok4" << endl;
                        for (int i = 0; i < M; i++) {
                            if (dead[2][i]) continue;
                            int r;
                            while (true) {
                                r = tmp_engine.rand()%5;
                                if (in_board(now_monsters[2*i]+dy[r], now_monsters[2*i+1]+dx[r])) break;
                            }
                            now_monsters[2*i] += dy[r];
                            now_monsters[2*i+1] += dx[r];
                            board[2][now_monsters[2*i]][now_monsters[2*i+1]]++;
                        }
                        /*
                        if (debug < 10) {
                            debug++;
                            for (int i = 0; i < 3; i++) {
                                for (int j = 0; j < S; j++) {
                                    for (int k = 0; k < S; k++) {
                                        cerr << board[i][j][k] << " ";
                                    }
                                    cerr << endl;
                                }
                                cerr << endl;
                            }
                        }
                        */
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            int cntK = board[0][y][x];
                            int cntM = board[2][y][x];
                            if (cntK == 0 || cntM == 0) continue;
                            pair<int,int> result = battle(cntK, cntM);
                            
                            board[0][y][x] -= (cntK-result.first);
                            last_dead[0][y][x] = cntK-result.first;
                            board[2][y][x] -= (cntM-result.second);
                            last_dead[2][y][x] = cntM-result.second;
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            if (last_dead[0][y][x] > 0) {
                                dead[0][i] = true;
                                last_dead[0][y][x]--;
                                status[i] = -1;
                            }
                        }
                        //cerr << "ok5" << endl;
                        for (int i = 0; i < M; i++) {
                            if (dead[2][i]) continue;
                            int y = now_monsters[2*i], x = now_monsters[2*i+1];
                            if (last_dead[2][y][x] > 0) {
                                dead[2][i] = true;
                                last_dead[2][y][x]--;
                                nowM--;
                            }
                        }
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            int y = now_princesses[2*i], x = now_princesses[2*i+1];
                            if (board[2][y][x]) {
                                dead[1][i] = true;
                                board[1][y][x]--;
                                nowP--;
                            }
                        }
                        for (int i = 0; i < KK; i++) {
                            if (dead[0][i]) continue;
                            status[i] = 0;
                            int y = now_knights[2*i], x = now_knights[2*i+1];
                            if (board[1][y][x]) {
                                status[i] = board[1][y][x];
                                board[1][y][x] = 0;
                                board[0][y][x] = i+1;
                            }
                        }
                        for (int i = 0; i < P; i++) {
                            if (dead[1][i]) continue;
                            int y = now_princesses[2*i], x = now_princesses[2*i+1];
                            if (board[0][y][x] > 0) {
                                follow[i] = board[0][y][x]-1;
                            }
                        }
                        /*
                        if (debug < 50) {
                            debug++;
                            for (int ii = 0; ii < status.size(); ii++) {
                                cerr << status[ii] << " ";
                            }
                            cerr << endl;
                        }
                        */
                    }
                    int this_score = 0;
                    for (int i = 0; i < KK; i++) {
                        if (status[i] == -1) this_score -= 10;
                        if (status[i] > 0) this_score += status[i]*100;
                    }
                    score[u][v] += this_score;
                }
            }
        }
        //cerr << "monte " << monte << endl;
        best_score = -INF;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 5; j++) {
                //cerr << best_score << " ";
                if (score[i][j] > best_score) {
                    best_score = score[i][j];
                    best_engine = XorShift(rand_seed[i][j]);
                }
            }
            //cerr << endl;
        }
        
        dynamic_init(princesses, (int)(split!=0), KK, _G, split);
        //cerr << split << " " << _G << endl;
        //cerr << "init end" << endl;
        //cerr << string(K[0], (char)('0'+rec_index[0]))+string(K[1], (char)('0'+rec_index[1])) << endl;
        if (split == 0) return string(K[0], (char)('0'+rec_index[0]));
        else return string(K[0], (char)('0'+rec_index[0]))+string(K[1], (char)('0'+rec_index[1]));
    }
    
    string go_rectangle (int ind, XorShift now_engine) {
        //cerr << "go_rectangle" << endl;
        int r = now_engine.rand()%2;
        int dir;
        string ret;
        if (rec_index[ind] == 0) {
            if (knights[ind][0] == rec_edge[0]) dir = 1;
            else if (knights[ind][1] == rec_edge[3]) dir = 2;
            else dir = (r?1:2);
            for (int i = 0; i < K[ind]; i++) {
                knights[ind][i*2] += dy[dir];
                knights[ind][i*2+1] += dx[dir];
            }
            for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]);
            if (knights[ind][0] == rec_edge[0] && knights[ind][1] == rec_edge[3]) {
                age[ind]++;
                age_first_day[ind] = true;
            }
        } else if (rec_index[ind] == 1) {
            if (knights[ind][0] == rec_edge[0]) dir = 3;
            else if (knights[ind][1] == rec_edge[1]) dir = 2;
            else dir = (r?3:2);
            for (int i = 0; i < K[ind]; i++) {
                knights[ind][i*2] += dy[dir];
                knights[ind][i*2+1] += dx[dir];
            }
            for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]);
            if (knights[ind][0] == rec_edge[0] && knights[ind][1] == rec_edge[1]) {
                age[ind]++;
                age_first_day[ind] = true;
            }
        } else if (rec_index[ind] == 2) {
            if (knights[ind][0] == rec_edge[2]) dir = 3;
            else if (knights[ind][1] == rec_edge[1]) dir = 0;
            else dir = (r?3:0);
            for (int i = 0; i < K[ind]; i++) {
                knights[ind][i*2] += dy[dir];
                knights[ind][i*2+1] += dx[dir];
            }
            for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]);
            if (knights[ind][0] == rec_edge[2] && knights[ind][1] == rec_edge[1]) {
                age[ind]++;
                age_first_day[ind] = true;
            }
        } else {
            if (knights[ind][0] == rec_edge[2]) dir = 1;
            else if (knights[ind][1] == rec_edge[3]) dir = 0;
            else dir = (r?1:0);
            for (int i = 0; i < K[ind]; i++) {
                knights[ind][i*2] += dy[dir];
                knights[ind][i*2+1] += dx[dir];
            }
            for (int i = 0; i < K[ind]; i++) ret.push_back(dir_str[dir]);
            if (knights[ind][0] == rec_edge[2] && knights[ind][1] == rec_edge[3]) {
                age[ind]++;
                age_first_day[ind] = true;
            }
        }
        rectangle[knights[ind][0]][knights[ind][1]] += K[ind];
        //cerr << "end_go_rectagle" << endl;
        return ret;
    }
    
    string draw_rectangle (vector<int> status, int ind, XorShift now_engine) {
        //cerr << "draw_rectangle" << endl;
        if (age_first_day[ind]) {
            Gsize[ind] = 0;
            int entity_cnt = 0;
            memset(Gindex[ind], 0, sizeof(Gindex[ind]));
            for (int i = 0; i < K[ind]; i++) {
                Gindex[ind][i] = Gsize[ind];
                if (status[i] != -1) {
                    entity_cnt++;
                    if (age[ind] > 1  && Gsize[ind] == 0) {
                        if (entity_cnt == min(G[ind],mainG)) {
                            Gsize[ind]++;
                            entity_cnt = 0;
                        }
                    } else if (entity_cnt == G[ind]) {
                        Gsize[ind]++;
                        entity_cnt = 0;
                    }
                }
            }
            if (Gsize[ind] == 0) Gsize[ind] = 1;
            for (int i = 0; i < K[ind]; i++) {
                if (Gindex[ind][i] == Gsize[ind]) Gindex[ind][i] = 0;
            }
            for (int i = 0; i < Gsize[ind]; i++) {
                Gknights[ind][2*i] = knights[ind][0];
                Gknights[ind][2*i+1] = knights[ind][1];
            }
        }
        //cerr << "mid_draw" << endl;
        string ret;
        for (int i = 0; i < Gsize[ind]; i++) {
            //cerr << "0 ";
            int r = now_engine.rand()%2;
            int dir;
            //cerr << rec_dir[ind][0] << " " << rec_dir[ind][1] << " ";
            int toy[2] = {Gknights[ind][i*2]+dy[rec_dir[ind][0]], Gknights[ind][i*2]+dy[rec_dir[ind][1]]};
            int tox[2] = {Gknights[ind][i*2+1]+dx[rec_dir[ind][0]], Gknights[ind][i*2+1]+dx[rec_dir[ind][1]]};
            //cerr << "1 ";
            if (age_first_day[ind] && i > Gsize[ind]/2) {
                dir = 4;
            } else if (!in_rectangle(toy[0], tox[0]) && !in_rectangle(toy[1], tox[1])) {
                dir = 4;
            } else if (!in_rectangle(toy[0], tox[0])) {
                dir = rec_dir[ind][1];
            } else if (!in_rectangle(toy[1], tox[1])) {
                dir = rec_dir[ind][0];
            } else {
                if (rectangle[toy[0]][tox[0]] > rectangle[toy[1]][tox[1]]) {
                    dir = rec_dir[ind][1];
                } else if (rectangle[toy[0]][tox[0]] < rectangle[toy[1]][tox[1]]) {
                    dir = rec_dir[ind][0];
                } else {
                    dir = rec_dir[ind][r];
                }
            }
            //cerr << "2 ";
            Gdir[ind][i] = dir;
            Gknights[ind][2*i] += dy[dir];
            Gknights[ind][2*i+1] += dx[dir];
            rectangle[Gknights[ind][2*i]][Gknights[ind][2*i+1]]++;
            //cerr << "3" << endl;
        }
        //cerr << "hun" << endl;
        for (int i = 0; i < K[ind]; i++) {
            knights[ind][2*i] += dy[Gdir[ind][Gindex[ind][i]]];
            knights[ind][2*i+1] += dx[Gdir[ind][Gindex[ind][i]]];
            ret.push_back(dir_str[Gdir[ind][Gindex[ind][i]]]);
        }
        //cerr << "mid2_draw" << endl;
        
        age_first_day[ind] = false;
        
        rec_len[ind]--;
        if (rec_len[ind] < 0) {
            age[ind]++;
            G[ind]++;
            age_first_day[ind] = true;
            rec_dir[ind][0] = (rec_dir[ind][0]+2)%4;
            rec_dir[ind][1] = (rec_dir[ind][1]+2)%4;
            rec_len[ind] = 1+rec_edge[2]-rec_edge[0]+rec_edge[1]-rec_edge[3];
        }
        //cerr << "end_draw" << endl;
        return ret;
    }
    
    string end_game (int ind) {
        //cerr << "end_game" << endl;
        int rest_turn = end_turn-turn+1;
        if (last_phase[ind]) {
            for (int i = 0; i < 4; i++) {
                int dis = distance(knights[ind][0], knights[ind][1], corner[i][0], corner[i][1]);
                if (dis > rest_turn) continue;
                if (i <= 1) {
                    if (knights[ind][0] != 0) {
                        knights[ind][0]--;
                        return string(K[ind], dir_str[0]);
                    } else {
                        if (i == 0) {
                            knights[ind][1]--;
                            return string(K[ind], dir_str[3]);
                        } else {
                            knights[ind][1]++;
                            return string(K[ind], dir_str[1]);
                        }
                    }
                } else {
                    if (knights[ind][0] != S-1) {
                        knights[ind][0]++;
                        return string(K[ind], dir_str[2]);
                    } else {
                        if (i == 2) {
                            knights[ind][1]++;
                            return string(K[ind], dir_str[1]);
                        } else {
                            knights[ind][1]--;
                            return string(K[ind], dir_str[3]);
                        }
                    }
                }
            }
            return string(K[ind], dir_str[4]);
        }
        string ret = string(K[ind], 'O');
        for (int k = 0; k < K[ind]; k++) {
            for (int i = 0; i < 4; i++) {
                int dis = distance(knights[ind][k*2], knights[ind][k*2+1], corner[i][0], corner[i][1]);
                if (dis > rest_turn) continue;
                if (i <= 1) {
                    if (knights[ind][k*2] != 0) {
                        knights[ind][k*2]--;
                        ret[k] = 'N';
                    } else {
                        if (i == 0) {
                            knights[ind][2*k+1]--;
                            ret[k] = 'W';
                        } else {
                            knights[ind][2*k+1]++;
                            ret[k] = 'E';
                        }
                    }
                } else {
                    if (knights[ind][2*k] != S-1) {
                        knights[ind][2*k]++;
                        ret[k] = 'S';
                    } else {
                        if (i == 2) {
                            knights[ind][2*k+1]++;
                            ret[k] = 'E';
                        } else {
                            knights[ind][2*k+1]--;
                            ret[k] = 'W';
                        }
                    }
                }
                break;
            }
        }
        return ret;
    }
    
    inline string clean_monsters(int ind) {
        //cerr << "clean_monsters" << endl;
        last_phase[ind] = true;
        int dir;
        if (last_south[ind]) {
            if (last_east[ind]) {
                if (knights[ind][1] == S-2) {
                    if (knights[ind][0] == S-2) {
                        last_east[ind] = false;
                        last_south[ind] = false;
                        dir = 3;
                    } else {
                        last_east[ind] = false;
                        dir = 2;
                    }
                } else {
                    dir = 1;
                }
            } else {
                if (knights[ind][1] == 1) {
                    if (knights[ind][0] == S-2) {
                        last_east[ind] = true;
                        last_south[ind] = true;
                        dir = 1;
                    } else {
                        last_east[ind] = true;
                        dir = 2;
                    }
                } else {
                    dir = 3;
                }
            }
        } else {
            if (last_east[ind]) {
                if (knights[ind][1] == S-2) {
                    if (knights[ind][0] == 1) {
                        last_east[ind] = false;
                        last_south[ind] = true;
                        dir = 3;
                    } else {
                        last_east[ind] = false;
                        dir = 0;
                    }
                } else {
                    dir = 1;
                }
            } else {
                if (knights[ind][1] == 1) {
                    if (knights[ind][0] == 1) {
                        last_east[ind] = true;
                        last_south[ind] = true;
                        dir = 1;
                    } else {
                        last_east[ind] = true;
                        dir = 0;
                    }
                } else {
                    dir = 3;
                }
            }
        }
        /*
        for (int i = 0; i < K*2; i += 2) {
            knights[i] += dy[dir];
            knights[i+1] += dx[dir];
        }
        */
        knights[ind][0] += dy[dir];
        knights[ind][1] += dx[dir];
        return string(K[ind], dir_str[dir]);
    }
    
    // ----------------------------------------------
    string split_move (vector<int> status, int P, int M, int timeLeft, int ind, int nowP, int nowK, XorShift now_engine) {
        //cerr << "hoge" << endl;
        if (end_turn-turn <= S || timeLeft <= 500) {
            return end_game(ind);
        }
        if (age[ind] == 0) {
            return go_rectangle(ind, now_engine);
        }
        if (age_first_day[ind] == true && nowK < mainG) {
            return end_game(ind);
        }
        if (P-nowP > 0 || age_first_day[ind] == false) {
            return draw_rectangle(status, ind, now_engine);
        }
        if (nowK < mainG) return end_game(ind);
        return clean_monsters(ind);
    }
    
    string move (vector<int> status, int P, int M, int timeLeft) {
        turn++;
        //cerr << "split " << split << endl;
        int nowP = 0;
        int nowK = 0;
        for (int i = 0; i < status.size(); i++) {
            if (status[i] > 0) nowP += status[i];
            if (status[i] >= 0) nowK++;
        }
        if (split == 0) {
            return split_move(status, P, M, timeLeft, 0, nowP, nowK, best_engine);
        } else {
            string tmp = split_move(vector<int>(status.begin(), status.begin()+K[0]), P, M, timeLeft, 0, nowP, nowK, best_engine)
                 + split_move(vector<int>(status.begin()+K[0], status.end()), P, M, timeLeft, 1, nowP, nowK, best_engine);
            //cerr << tmp << endl;
            return tmp;
            /*
            return split_move(vector<int>(status.begin(), status.begin()+k[0]), p, m, timeleft, 0)
                 + split_move(vector<int>(status.begin()+k[0], status.end()), p, m, timeleft, 1);
            */
        }
    }
};
// -------8<------- end of solution submitted to the website -------8<-------

template<class T> void getVector(vector<T>& v) {
    for (int i = 0; i < v.size(); ++i)
        cin >> v[i];
}

int main() {
    PrincessesAndMonsters pam;

    int S, P, M, K;
    cin >> S >> P;
    vector<int> princesses(P);
    getVector(princesses);
    cin >> M;
    vector<int> monsters(M);
    getVector(monsters);
    cin >> K;
    
    string retInit = pam.initialize(S, princesses, monsters, K);
    cout << retInit << endl;
    cout.flush();

    for (int st = 0; ; ++st) {
        int nK;
        cin >> nK;
        vector<int> status(K);
        getVector(status);
        int nP, nM;
        cin >> nP >> nM;
        int timeLeft;
        cin >> timeLeft;

        string ret = pam.move(status, nP, nM, timeLeft);
        cout << ret << endl;
        cout.flush();
    }
}