Farmer John et ses bovins danseurs exotiques répètent leur nouveau spectacle «La vache de rue nommée Désir». Pendant la répétition, ils forment $N$ $(1 \le N \le 1,000)$ piles de 30, chaque vache sur le dos d'une autre (elles sont extraordinaires). Le pré contient aussi $M$ $(1 \le M \le 1,000)$ meules ailleurs. Voici un agencement : C est une pile de 30 vaches, H une meule.

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

Chef d’orchestre, FJ possède quatre sifflets de tons différents. Ils commandent respectivement à la vache du bas de chaque pile, avec toutes celles dessus, de bouger d’une unité au nord, sud, est ou ouest.

À chaque entrée sur une case avec meule, la vache du sommet, même seule, saute sur la meule ; les autres passent sur la même case. Après 30 rencontres, avec des meules différentes ou répétées, la pile est épuisée et toutes sont sur des meules ou sur des vaches sur des meules. Chaque solide meule supporte un nombre illimité de vaches.

FJ regarde de l’autre côté du pré chez Farmer Don et voit avec horreur un grand réservoir exploser et une vague de lait vers les danseuses ! Les vaches sur les meules sont en sécurité. Il doit en sauver le plus possible, transformant la danse en sauvetage.

On donne $K$ $(1 \le K \le 30)$ coups de sifflet disponibles avant la vague et les positions $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ des $N$ piles et $M$ meules, encore sans vaches. Donnez le maximum sauvé et une séquence : E est, N nord, W ouest, S sud. Parmi les optimales, FJ veut la plus petite lexicographiquement. Piles et meules ne coïncident pas initialement dans l'entrée.

On peut aller partout, même hors du pré.

Entrée

• Ligne 1 : entiers $N$, $M$, $K$ séparés par espaces.
• Lignes $2,\ldots,N+1$ : ligne $i+1$, position $X$,$Y$ d'une pile de 30, deux entiers espacés $X_{i}$ et $Y_{i}$.
• Lignes $N+2,\ldots,N+M+1$ : ligne $i+N+1$, position $X$,$Y$ d'une meule, deux entiers espacés $X_{i}$ et $Y_{i}$.

Sortie

• Ligne 1 : un entier, maximum de vaches sauvées.
• Ligne 2 : $K$ caractères, séquence optimale la plus petite lexicographiquement.

Exemples

Entrée 1

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

Sortie 1

6
EEE

Remarque

Sifflez vers l’est trois fois, puis le lait inonde le pré. Chaque meule sauve une vache.

Auteur : Thomas Williamson, 2004