Avem o cameră dreptunghiulară de dimensiuni N × 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 (L1, C1) despre care se garantează că nu este pe marginea matricei, iar ușa de ieșire a camerei la coordonata (L2, C2) 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 patru direcții: Nord (codificată cu litera N), Sud (codificată cu litera S), Est (codificată cu litera E) sau Vest (codificată cu litera W).

Cerința

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 L1, C1, L2, C2, 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ă, fără 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 ≤ N, M ≤ 1.000
• 2 ≤ L1 ≤ N − 1
• 2 ≤ C1 ≤ M − 1
• L2 = 1 sau L2 = N
• C2 = 1 sau C2 = M

Exemplul 1:

Intrare

4 4
2 2 1 1

Ieșire

WSSENESENNNWWW

Explicație

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

Exemplul 2:

Intrare

5 6
3 3 5 1

Ieșire

EESSENNNNWSWNWSWNWSSESEESWWW

Explicație

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