Roboclean

Cerință

Avem o cameră dreptunghiulară de dimensiuni $N \cdot M$, pe care o vom interpreta ca o matrice cu $N$ linii și $M$ coloane, cu liniile numerotate de la 1 la $N$ de sus în jos și coloanele numerotate de la 1 la $M$ de la stânga la dreapta. Un aspirator robot se află inițial în poziția de coordonate $(L_1, C_1)$ despre care se garantează că nu este pe marginea matricei, iar ușa de ieșire a camerei la coordonata $(L_2, C_2)$ ce poate fi un colț de matrice, adică $(1, 1)$, $(1, M)$, $(N, 1)$ sau $(N, M)$.
Aspiratorul poate fi programat să se mute cu o poziție în cele 4 direcții: Nord (codificată cu litera $N$), Sud (codificată cu litera $S$), Est (codificată cu litera $E$) sau Vest (codificată cu litera $W$).

Scrieți un program care să afișeze o listă de instrucțiuni pentru aspirator astfel încât:

• să aspire o suprafață maximă în cameră
• să nu treacă de două ori prin aceeași celulă
• în final să ajungă în colțul camerei unde se află ușa.

Date de intrare

Datele de intrare conțin pe prima linie numerele naturale $N$ și $M$ reprezentând dimensiunile camerei. Pe cea de a doua linie se află numerele naturale $L_1, C_1, L_2, C_2$, reprezentând coordonatele poziției inițiale a robotului, respectiv coordonatele colțului în care se află ușa camerei. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Afișați o singură linie pe care va fi scrisă o succesiune de caractere din mulțimea ${N, S, E, W}$, codificând direcțiile de deplasare a robotului astfel încât să aspire o suprafață maximă în cameră, fară să treacă de două ori prin aceeași poziție, iar în final să ajungă în colțul camerei unde se află ușa.
Problema poate permite mai multe soluții. Orice soluție corectă se acceptă.

Restricții și precizări

• $4 \leq N, M \leq 1 \ 000$;
• $2 \leq L_1 \leq N - 1$;
• $2 \leq C_1 \leq M - 1$;
• $L_2 = 1$ sau $L_2 = N$
• $C_2 = 1$ sau $C_2 = M$
• Această problemă are scoruri individuale pe teste.

Exemplul 1

stdin

4 4
2 2 1 1

stdout

WSSENESENNNWWW

Explicație

Ordinea în care robotul parcurge pozițiile din matricea care reprezintă camera (unde cu $X$ am reprezentat o poziție pe care robotul nu a aspirat-o) este următoarea

15 14 13 12
2  1  X  11 
3  6  7  10
4  5  8  9

Exemplul 2

stdin

5 6
3 3 5 1

stdout

EESSENNNNWSWNWSWNWSSESEESWWW

Explicație

Ordinea în care robotul parcurge pozițiile din matrice este următoarea

19 18 15 14 11 10
20 17 16 13 12  9
21 22  1  2  3  8
X  23 24 25  4  7 
29 28 27 26  5  6