Farmer John e suas vacas dançarinas exóticas ensaiam o novo musical «A vaca de rua chamada Desejo». Num momento formam $N$ $(1 \le N \le 1,000)$ pilhas de 30, cada vaca no dorso de outra (são incríveis). O pasto também tem $M$ $(1 \le M \le 1,000)$ montes de feno em lugares separados. Exemplo: C é pilha de 30 vacas, H monte de feno.

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

Como maestro, FJ tem quatro apitos de tons distintos que mandam a vaca inferior de cada pilha, junto de todas acima, mover uma unidade ao norte, sul, leste ou oeste respectivamente.

Ao entrar numa célula com feno, a vaca do topo, mesmo sozinha, salta ao feno e as outras entram na mesma célula. Após 30 encontros, com montes distintos ou repetidos, a pilha acaba: todas ficam no feno ou em vacas no feno. Cada monte firme suporta vacas ilimitadas.

FJ olha para a ordenha de Farmer Don do outro lado do pasto e vê horrorizado um tanque enorme explodir, enviando onda de leite às dançarinas! Vacas no feno estão seguras. Deve salvar o máximo transformando a dança em técnica de salvamento.

Dados $K$ $(1 \le K \le 30)$ apitos antes da onda e posições $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ das $N$ pilhas e $M$ montes, ainda sem vacas, ache o máximo salvo e sequência. Use E leste, N norte, W oeste, S sul. Entre ótimas quer a menor lexicograficamente. Posições iniciais de pilhas e feno não coincidem na entrada.

Podem ir a qualquer lugar, inclusive fora do pasto.

Entrada

• Linha 1: inteiros $N$, $M$, $K$ com espaços.
• Linhas $2,\ldots,N+1$: linha $i+1$ dá posição $X$,$Y$ de pilha de 30, dois inteiros com espaço $X_{i}$ e $Y_{i}$.
• Linhas $N+2,\ldots,N+M+1$: linha $i+N+1$ dá posição $X$,$Y$ do feno, dois inteiros com espaço $X_{i}$ e $Y_{i}$.

Saída

• Linha 1: inteiro com máximo de vacas salvas.
• Linha 2: $K$ caracteres, sequência ótima menor lexicograficamente.

Exemplos

Entrada 1

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

Saída 1

6
EEE

Nota

Apita para leste três vezes, depois o leite inunda o pasto. Cada monte salva uma vaca.

Autor: Thomas Williamson, 2004