Farmer John y sus exóticas vacas bailarinas ensayan el nuevo musical «La vaca callejera llamada Deseo». En un momento forman $N$ $(1 \le N \le 1,000)$ pilas de 30, cada vaca en el lomo de otra (son asombrosas). El pasto también tiene $M$ $(1 \le M \le 1,000)$ montones de heno en otros lugares. Ejemplo: C es una pila de 30 vacas, H un montón de heno.

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

Como director, FJ tiene cuatro silbatos de tonos distintos que ordenan a la vaca inferior de cada pila, junto con todas encima, moverse una unidad al norte, sur, este u oeste respectivamente.

Al entrar en una celda con heno, la vaca superior, incluso si queda sola, salta al heno; las restantes entran en la misma celda. Tras 30 encuentros, con heno distinto o repetido, la pila se agota: todas están sobre heno o sobre vacas sobre heno. Cada sólido montón sostiene ilimitadas vacas.

FJ mira al otro lado del pasto las instalaciones de ordeño de Farmer Don y ve horrorizado un gran tanque explotar y una ola de leche hacia las bailarinas. Las que están sobre heno están seguras: debe salvar el máximo, transformando el baile en técnica salvavidas.

Dados $K$ $(1 \le K \le 30)$ silbidos antes de la ola y las posiciones $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ de $N$ pilas y $M$ montones, sin vacas encima aún, halla el máximo salvado y la secuencia. Usa E este, N norte, W oeste, S sur. Entre óptimas quiere la menor lexicográficamente. Posiciones iniciales de pilas y heno no coinciden en la entrada.

Pueden moverse a cualquier lugar, fuera del pasto también.

Entrada

• Línea 1: enteros $N$, $M$, $K$ separados por espacios.
• Líneas $2,\ldots,N+1$: línea $i+1$, posición $X$,$Y$ de una pila de 30, dos enteros con espacio $X_{i}$, $Y_{i}$.
• Líneas $N+2,\ldots,N+M+1$: línea $i+N+1$, posición $X$,$Y$ de heno, dos enteros con espacio $X_{i}$, $Y_{i}$.

Salida

• Línea 1: entero con máximo de vacas salvadas.
• Línea 2: $K$ caracteres, secuencia óptima menor lexicográficamente.

Ejemplos

Entrada 1

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

Salida 1

6
EEE

Nota

Silba al este tres veces, luego la leche inunda el área. Cada montón salva una vaca.

Autor: Thomas Williamson, 2004