POLSKI SPOJ

Jaś, odkąd pamiętają jego rodzice, przejawiał zainteresowanie do wszelkich pojazdów na czterech kółkach i do... łamigłówek matematycznych. Rodzina Jasia, podobnie jak i ich sąsiedzi, mają duże ogrody wymagające częstej pielęgnacji. Postanowili zatem połączyć zamiłowania Jasia i sprezentowali mu najnowszy model kosiarki do trawy. Odtąd Jaś wytycza nowe trasy w ogrodach swoich rodziców i sąsiadów, optymalizując czasy ich przejazdów, przy okazji kosząc im trawę...

Wejście

Każdy ogród podzielony jest na pola kwadratowe o wymiarze jednostkowym. Jaś porusza się pomiędzy sąsiednimi polami, w dowolnym z czterech kierunków. Zakładać będziemy, że ogród nie posiada wewnątrz żadnych innych pól niż trawnik, który musi zostać skoszony. Zaczynając ze wskazanego pola, Jaś musi skosić cały ogród i powrócić do punktu startu, minimalizując przy tym łączną długość drogi. W pierwszej linii podana jest informacja o liczbie ogrodów (zestawów testowych), t <= 10. W każdym zestawie testowym, w pierwszej linijce podana jest łączna ilość odcinków z brzegu ogrodu, 4 <= n <= 20000. Druga linia zawiera dokładnie n liczb całkowitych a₁,...,a_n opisujących długości kolejnych odcinków z brzegu ogrodu (1 <= |a_i| <= 250). Każde dwa kolejne odcinki z brzegu ogrodu są do siebie prostopadłe. Długość i-tego odcinka jest równa wartości bezwględnej a_i, znak określa kierunek: "+" oznacza N lub E, "-" oznacza S lub W, zakładając, że ogród obchodzi się dookoła zgodnie ze wskazówkami zegara. Pole początkowe wskazane jest przez początek pierwszego odcinka z brzegu ogrodu, który jest podany w kierunku N/S. Przyjmiemy, że cały ogród mieści się w kwadracie 1000 x 1000.

Wyjście

Na wyjściu należy podać liczbe oraz sekwencje ruchów kosiarki Jasia z wykorzystaniem informacji o kierunkach N, S, E oraz W, zaczynając od pierwszego pola (początek pierwszego odcinka z brzegu).

Punktacja

Każdy zestaw testowy będzie punktowany niezależnie. Za wynik punktowy danego zestawu testowego przyjęty będzie stosunek długości trasy Jasia do całkowitej liczby pól w ogrodzie. Łączny wynik będzie sumą wszystkich wyników uzyskanych z poszczególnych testów. Dokładny wzór:

sum(max{(3 - score_i)*3,0},i=1,2,3)

Przykład

Wejście:
5
12
+1 +1 +1 +1 -1 +1 -1 -1 -1 -1 +1 -1
4
+2 +1 -2 -1
14
+2 +1 +2 +2 -1 +2 -3 -1 +1 -1 +1 -1 -2 -2
8
-2 -1 +1 -3 +2 +3 -1 +1
12
+7 +1 -3 +1 +3 +1 -7 -1 +1 -1 -1 -1

Wyjście:
8 ENSEWSNW
2 NS
18 NENNESEESSNWNWWSSW
10 WWWNEESESN
26 NNNNNNSSSEENNNSSSSSSNNWSWS

Wynik:
1.353