يتدرب 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