Farmer John cùng đàn bò nhảy múa kỳ lạ tập nhạc kịch mới «Bò đường phố mang tên Khát vọng». Giữa buổi tập, chúng xếp $N$ $(1 \le N \le 1,000)$ chồng, mỗi chồng 30 con đứng lên lưng nhau (thật phi thường). Đồng còn có $M$ $(1 \le M \le 1,000)$ đống cỏ ở vị trí riêng. Ví dụ: C là chồng 30 bò, H đống cỏ.

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

Là nhạc trưởng, FJ có bốn còi âm khác nhau, lần lượt ra lệnh con dưới mỗi chồng cùng mọi con trên di chuyển một đơn vị bắc, nam, đông hoặc tây.

Mỗi khi vào ô có đống cỏ, con trên cùng dù chỉ còn một sẽ nhảy lên cỏ, các con còn lại vào cùng ô. Sau 30 lần gặp cỏ, khác nhau hay lặp lại, chồng hết: tất cả đứng trên cỏ hoặc trên bò đứng trên cỏ. Mỗi đống vững chắc đỡ số bò vô hạn.

FJ nhìn qua đồng tới cơ sở vắt sữa Farmer Don và kinh hoàng thấy bồn lớn nổ, sóng sữa khổng lồ tiến đến bò diễn! Bò trên cỏ an toàn. Phải cứu nhiều nhất, biến điệu múa thành kỹ thuật cứu mạng.

Cho số lần thổi còi $K$ $(1 \le K \le 30)$ trước sóng và vị trí $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ của $N$ chồng bò, $M$ đống cỏ chưa có bò. Tìm số cứu tối đa và chuỗi còi. E đông, N bắc, W tây, S nam; chọn nhỏ nhất từ điển trong các chuỗi tối ưu. Vị trí ban đầu của bò và cỏ không trùng nhau trong dữ liệu.

Có thể đi mọi nơi, kể cả ngoài đồng.

Dữ liệu vào

• Dòng 1: số nguyên $N$, $M$, $K$ cách nhau dấu cách.
• Dòng $2,\ldots,N+1$: dòng $i+1$ mô tả vị trí $X$,$Y$ chồng 30 bò bằng hai số nguyên cách nhau dấu cách $X_{i}$, $Y_{i}$.
• Dòng $N+2,\ldots,N+M+1$: dòng $i+N+1$ mô tả vị trí $X$,$Y$ đống cỏ bằng hai số nguyên cách nhau dấu cách $X_{i}$, $Y_{i}$.

Dữ liệu ra

• Dòng 1: số nguyên là số bò cứu tối đa.
• Dòng 2: $K$ ký tự, chuỗi tối ưu nhỏ nhất từ điển.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

6
EEE

Ghi chú

Thổi hướng đông ba lần rồi sữa ngập đồng. Mỗi đống cứu một bò.

Tác giả: Thomas Williamson, 2004