Farmer John과 이국적인 춤추는 소들은 새 뮤지컬 ‘욕망이라는 이름의 길거리 소’를 연습합니다. 도중에 소가 다른 소 등에 서서 30마리씩 $N$ $(1 \le N \le 1,000)$더미를 이룹니다(놀라운 소들입니다). 목초지에는 다른 위치에 건초 더미 $M$ $(1 \le M \le 1,000)$개도 있습니다. 배치 예에서 C는 소 30마리 더미, H는 건초입니다.

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

지휘자인 FJ의 서로 다른 음의 네 호루라기는 각각 각 더미 맨 아래 소와 그 위 모두를 북, 남, 동, 서 중 해당 방향으로 한 단위 움직입니다.

건초 있는 칸에 들어갈 때마다 맨 위 소는 한 마리만 남았어도 건초로 뛰고 나머지는 같은 칸으로 갑니다. 아래 소가 건초를 30번 만나면 서로 달라도 같아도 더미는 없어지고 모두 건초나 건초 위 소 위에 섭니다. 튼튼한 각 건초 더미는 무한히 많은 소를 지탱합니다.

FJ는 목초지 건너 Farmer Don의 착유 시설을 보고 거대한 우유 통이 터져 춤추는 소에게 우유 파도가 오는 것을 공포 속에 봅니다! 건초 위는 안전하므로 단순한 춤을 구조 기술로 바꿔 최대한 많은 소를 구해야 합니다.

파도 전 불 수 있는 횟수 $K$ $(1 \le K \le 30)$와 소 더미 $N$개, 건초 $M$개의 위치 $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$가 주어집니다. 아직 건초 위 소는 없습니다. 최대 구조 수와 호루라기 순서를 구하세요. E 동, N 북, W 서, S 남이며 최적 순서 중 사전순 최소를 원합니다. 입력의 소와 건초 초기 위치는 겹치지 않습니다.

목초지 밖을 포함해 어디로든 갈 수 있습니다.

입력

• 1행: 공백 구분 정수 $N$, $M$, $K$.
• $2,\ldots,N+1$행: $i+1$행이 소 30마리 더미의 $X$,$Y$ 위치를 공백 구분 정수 $X_{i}$와 $Y_{i}$로 나타냅니다.
• $N+2,\ldots,N+M+1$행: $i+N+1$행이 건초의 $X$,$Y$ 위치를 공백 구분 정수 $X_{i}$와 $Y_{i}$로 나타냅니다.

출력

• 1행: 구할 수 있는 최대 소 수인 정수.
• 2행: $K$문자, 최대 구조를 달성하는 사전순 최소 명령 순서.

예제

입력 1

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

출력 1

6
EEE

참고

동쪽 호루라기를 세 번 불고 나면 우유가 덮칩니다. 각 건초는 한 마리를 구합니다.

문제 제작: Thomas Williamson, 2004