Farmer John i jego egzotyczne tańczące krowy ćwiczą musical „Uliczna krowa zwana Pożądaniem”. Podczas próby tworzą $N$ $(1 \le N \le 1,000)$ stosów po 30, stojąc na grzbietach (są niesamowite). Na pastwisku jest też $M$ $(1 \le M \le 1,000)$ stogów w innych miejscach. Przykład: C to stos 30 krów, H stóg.

                8 .........
                7 ....CH.H.         C = stack of 30 cows
                6 .........
                5 .........         H = haystack
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

Jako dyrygent FJ ma cztery gwizdki o różnych tonach. Każdy nakazuje dolnej krowie każdego stosu wraz ze wszystkimi ponad nią krok o jednostkę na północ, południe, wschód lub zachód odpowiednio.

Przy wejściu na pole ze stogiem najwyższa, choćby jedyna, wskakuje na stóg, pozostałe wchodzą na to samo pole. Po 30 spotkaniach ze stogami, różnymi lub powtarzanymi, stos znika: wszystkie są na stogach albo krowach na stogach. Każdy mocny stóg mieści nieograniczoną liczbę krów.

FJ patrzy przez pastwisko na mleczarnię Farmer Don i z przerażeniem widzi wybuch ogromnego zbiornika i falę mleka ku tańczącym! Krowy na stogach są bezpieczne. Musi uratować jak najwięcej, zmieniając taniec w technikę ratunkową.

Dane $K$ $(1 \le K \le 30)$ gwizdnięć przed falą oraz pozycje $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ stosów $N$ i stogów $M$, jeszcze bez krów. Znajdź maksimum uratowanych i sekwencję. E wschód, N północ, W zachód, S południe; wśród optymalnych najmniejszą leksykograficznie. Początkowe pozycje krów i stogów w wejściu nie pokrywają się.

Można chodzić wszędzie, także poza pastwiskiem.

Wejście

• Wiersz 1: całkowite $N$, $M$, $K$ ze spacjami.
• Wiersze $2,\ldots,N+1$: wiersz $i+1$, pozycja $X$,$Y$ stosu 30 krów, dwie całkowite $X_{i}$, $Y_{i}$ ze spacją.
• Wiersze $N+2,\ldots,N+M+1$: wiersz $i+N+1$, pozycja $X$,$Y$ stogu, dwie całkowite $X_{i}$, $Y_{i}$ ze spacją.

Wyjście

• Wiersz 1: całkowita, maksimum uratowanych krów.
• Wiersz 2: $K$ znaków, najmniejsza leksykograficznie optymalna sekwencja.

Przykład

Wejście 1

3 6 3
3 4
6 2
5 7
8 2
9 2
6 4
5 4
6 7
8 7

Wyjście 1

6
EEE

Uwagi

Gwiżdż na wschód trzy razy, potem mleko zaleje teren. Każdy stóg uratuje krowę.

Autor: Thomas Williamson, 2004