Farmer John und seine exotischen tanzenden Kühe proben das neue Musical „Die Straßenkuh namens Sehnsucht“. Dabei bilden sie $N$ $(1 \le N \le 1,000)$ Stapel zu 30, jede auf dem Rücken einer anderen (erstaunliche Kühe). Auf der Weide stehen außerdem $M$ $(1 \le M \le 1,000)$ Heuhaufen an anderen Stellen. Beispiel: C ist ein Stapel aus 30 Kühen, H ein Heuhaufen.

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

Als Dirigent hat FJ vier Pfeifen verschiedener Töne. Jede befiehlt der untersten Kuh jedes Stapels mitsamt allen darüber, eine Einheit nach Norden, Süden, Osten beziehungsweise Westen zu gehen.

Beim Betreten einer Zelle mit Heuhaufen springt die oberste Kuh, selbst wenn allein, darauf; die übrigen betreten dieselbe Zelle. Nach 30 Begegnungen, mit verschiedenen oder gleichen Haufen, ist der Stapel aufgebraucht: alle stehen auf Heu oder auf Kühen auf Heu. Jeder stabile Haufen trägt beliebig viele Kühe.

FJ schaut über die Weide zu Farmer Dons Melkanlage und sieht entsetzt einen riesigen Milchtank explodieren und eine Milchwelle auf die Tänzerinnen zurollen! Auf Heu sind Kühe sicher. Er muss möglichst viele retten und den Tanz zur Rettungstechnik machen.

Gegeben sind $K$ $(1 \le K \le 30)$ Pfiffe bis zur Welle sowie Positionen $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ der $N$ Stapel und $M$ Haufen, auf denen noch keine Kuh steht. Finde die größte gerettete Zahl und eine Pfiffsequenz. E Osten, N Norden, W Westen, S Süden; unter optimalen die lexikografisch kleinste. Anfangspositionen von Kühen und Heu fallen in der Eingabe nicht zusammen.

Kühe dürfen überallhin, auch außerhalb der Weide.

Eingabe

• Zeile 1: ganze Zahlen $N$, $M$, $K$ mit Leerzeichen.
• Zeilen $2,\ldots,N+1$: Zeile $i+1$, $X$,$Y$-Position eines 30er-Stapels, zwei ganze Zahlen mit Leerzeichen $X_{i}$, $Y_{i}$.
• Zeilen $N+2,\ldots,N+M+1$: Zeile $i+N+1$, $X$,$Y$-Position eines Heuhaufens, zwei ganze Zahlen mit Leerzeichen $X_{i}$, $Y_{i}$.

Ausgabe

• Zeile 1: ganze Zahl, größte gerettete Kuhzahl.
• Zeile 2: $K$ Zeichen, lexikografisch kleinste optimale Befehlsfolge.

Beispiele

Eingabe 1

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

Ausgabe 1

6
EEE

Hinweis

Pfeife dreimal nach Osten; dann überschwemmt Milch die Weide. Jeder Haufen rettet eine Kuh.

Autor: Thomas Williamson, 2004