농장의 위기

문제

농부 존과 이국적인 춤을 추는 소 떼가 새 뮤지컬 "욕망이라는 이름의 젖소"를 연습하고 있다. 연습 도중, 소들은 정확히 30마리씩 쌓인 $N$개($1 \le N \le 1000$)의 더미로 배치되어 있다. 한 마리가 다른 소의 등 위에 올라선 형태다(놀라운 재능을 가진 소들이다). 목초지에는 서로 다른 위치에 $M$개($1 \le M \le 1000$)의 건초 더미도 놓여 있다. 배치의 한 예:

                8 .........
                7 ....CH.H.         C = 소 30마리 더미
                6 .........
                5 .........         H = 건초 더미
                4 ..C.HH...
                3 .........
                2 .....C.HH
                1 .........
                  123456789

지휘자인 농부 존에게는 호루라기 네 개가 있다. 하나는 모든 더미의 맨 아래 소에게 (그 위에 쌓인 모든 소를 데리고) 북쪽으로 한 칸 이동하라고 명령하고, 나머지 셋은 각각 남쪽, 동쪽, 서쪽으로 이동시킨다. 호루라기를 한 번 불면 모든 더미가 동시에 같은 방향으로 이동한다.

더미가 건초 더미가 있는 칸에 들어설 때마다, 그 더미의 맨 위 소가(더미 높이가 1이어도) 건초 더미 위로 뛰어오르고, 나머지 소들은 그 건초 더미가 있는 칸으로 계속 이동한다. 따라서 한 더미가 건초 더미에 30번 들어서면(같은 건초 더미에 반복해서든, 서로 다른 건초 더미든) 그 더미의 소는 모두 소진되어, 모든 소가 건초 더미 위(또는 이미 건초 더미 위에 있는 소 위)에 안전하게 서 있게 된다. 건초 더미 하나는 소를 몇 마리든 떠받칠 수 있다.

그때 이웃 농장의 우유 탱크가 터지면서 거대한 우유 해일이 목초지로 밀려온다. 건초 더미 위에 있는 소는 안전하지만, 그 밖의 소는 모두 휩쓸린다. 농부 존은 해일이 도달하기 전까지 호루라기를 정확히 $K$번($1 \le K \le 30$) 더 불 수 있다.

$K$와 $N$개 소 더미 및 $M$개 건초 더미의 위치($1 \le X_i \le 1000$, $1 \le Y_i \le 1000$; 처음에 소가 올라가 있는 건초 더미는 없고, 소 더미와 건초 더미는 같은 칸을 공유하지 않는다)가 주어질 때, 구할 수 있는 소의 최대 수와 이를 달성하는 호루라기 순서를 출력하라. 방향은 'E'(동), 'N'(북), 'W'(서), 'S'(남)로 표기한다. 소를 최대로 구하는 모든 순서 중에서 사전순으로 가장 작은 것을 출력한다. 더미는 목초지 바깥을 포함해 어느 칸으로든 이동할 수 있다.

입력

첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $K$.
2번째 줄부터 $N+1$번째 줄까지: 소 30마리 더미의 위치를 나타내는 두 정수 $X_i$와 $Y_i$ (공백으로 구분).
$N+2$번째 줄부터 $N+M+1$번째 줄까지: 건초 더미의 위치를 나타내는 두 정수 $X_i$와 $Y_i$ (공백으로 구분).

출력

첫째 줄: 구할 수 있는 소의 최대 수를 나타내는 정수 하나.
둘째 줄: 그만큼의 소를 구하는, 사전순으로 가장 작은 호루라기 명령 순서. 정확히 $K$개의 문자.

힌트

호루라기 한 번은 모든 더미를 같은 방향으로 움직이므로, 중요한 것은 누적 이동량뿐이다. 각 더미는 그 누적 이동량이 건초 더미 위에 놓일 때마다 소 한 마리를 구한다. 모든 더미를 한 방향으로 곧게 보내면 여러 건초 더미를 한꺼번에 훑을 수 있고, 같은 건초 더미 칸을 다시 지날 때마다 소를 한 마리씩 더 구한다.