Farmer John ועדר הפרות הרוקדות האקזוטיות מתאמנים למחזמר החדש ״פרת הרחוב ושמה תשוקה״. במהלך החזרה הן נערמות ב-$N$ $(1 \le N \le 1,000)$ ערמות של 30, אחת על גב השנייה (פרות מדהימות). יש גם $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)$ שריקות לפני הגל ומיקומי $X_{i}$, $Y_{i}$ $(1 \le X_{i} \le 1,000; 1 \le Y_{i} \le 1,000)$ של $N$ ערמות פרות ו-$M$ ערמות חציר שעדיין אין עליהן פרות. מצאו מספר מרבי ורצף שריקות. E מזרח, N צפון, W מערב, S דרום; מבין האופטימליים הקטן לקסיקוגרפית. מיקומי הפרות והחציר ההתחלתיים אינם חופפים בקלט.

אפשר ללכת לכל מקום, גם מחוץ למרעה.

קלט

• שורה 1: שלמים $N$, $M$, $K$ ברווחים.
• שורות $2,\ldots,N+1$: שורה $i+1$ נותנת מיקום $X$,$Y$ של ערמת 30 פרות בשני שלמים ברווח $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