JOI משתתף באירוע חברתי של IOI. באירוע סודרו כריכים על רשת של משבצות ריבועיות בעלת $R$ שורות ו־$C$ עמודות. כל כריך הוא בצורת משולש ישר־זווית ושווה־שוקיים, שאורך שתי שוקיו שווה לאורך צלע של משבצת. בכל משבצת הונחו שני כריכים כך שהיתרים שלהם נוגעים זה בזה. האיור הבא מציג דוגמה לסידור הכריכים.

איור 1. דוגמה לסידור הכריכים

אי אפשר לקחת כריך שמקיים את שני התנאים הבאים בו־זמנית.

• היתר שלו נוגע בכריך אחר שטרם נלקח.
• לפחות אחת משתי הצלעות שאינן היתר נוגעת בכריך אחר שטרם נלקח.

אפשר לקחת כל כריך אחר.

המצב שבו עדיין לא נלקח אף כריך נקרא המצב ההתחלתי. כדי לקחת כריך מסוים החל מהמצב ההתחלתי, ייתכן שיהיה צורך לקחת קודם כמה כריכים אחרים. בהתאם לסידור הכריכים, ייתכן שיש כריכים שאי אפשר לקחת כלל.

JOI רוצה לאכול את שני הכריכים שנמצאים באותה משבצת. הוא עדיין לא החליט מאיזו משבצת יאכל את הכריכים.

הוא תוהה מהו המספר המזערי של כריכים שיש לקחת החל מהמצב ההתחלתי כדי לקחת את שני הכריכים שבמשבצת מסוימת.

המשימה

בהינתן סידור הכריכים, כתבו תוכנית שתקבע עבור כל משבצת אם אפשר לקחת את שני הכריכים שבה באמצעות לקיחת כריכים החל מהמצב ההתחלתי, ואם הדבר אפשרי, תחשב את המספר המזערי של כריכים שיש לקחת. בספירה יש לכלול גם את שני הכריכים המבוקשים עצמם.

קלט

קראו את הנתונים הבאים מהקלט הסטנדרטי.

• השורה הראשונה מכילה את המספרים השלמים $R$, $C$, מופרדים ברווח. הם מציינים שהכריכים מסודרים על רשת של משבצות ריבועיות בעלת $R$ שורות ו־$C$ עמודות.
• השורה ה־$i$ מבין $R$ השורות הבאות ($1 \le i \le R$) מכילה מחרוזת באורך $C$. כל תו הוא N או Z. התו ה־$j$ משמאל ($1 \le j \le C$) במחרוזת מציין את סידור הכריכים במשבצת שבשורה ה־$i$ מלמעלה ובעמודה ה־$j$ משמאל. התווים N ו־Z מציינים, בהתאמה, את הסידורים הבאים.

איור 2. סידור הכריכים בכל משבצת

פלט

הדפיסו $R$ שורות לפלט הסטנדרטי. בשורה ה־$i$ ($1 \le i \le R$) הדפיסו $C$ מספרים שלמים מופרדים ברווחים. כמספר ה־$j$ ($1 \le j \le C$), הדפיסו את המספר המזערי של כריכים שיש לקחת כדי לקחת את שני הכריכים שבמשבצת בשורה ה־$i$ מלמעלה ובעמודה ה־$j$ משמאל. אם אי אפשר לקחת אותם, הדפיסו $-1$.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $1 \le R \le 400$.
• $1 \le C \le 400$.

תתי־משימות

תת־משימה 1 [35 נקודות]

מתקיימים התנאים הבאים.

• $R \le 50$.
• $C \le 50$.

תת־משימה 2 [65 נקודות]

אין מגבלות נוספות.

דוגמאות

קלט 1

2 3
NZN
ZZN

פלט 1

10 8 2
8 6 4

הסבר

סידור הכריכים בדוגמת קלט 1 מתאים לאיור 1 שבנוסח השאלה.

לדוגמה, כדי לקחת את שני הכריכים שבמשבצת בשורה השנייה מלמעלה ובעמודה השנייה משמאל, אפשר לקחת כריכים בסדר הבא.

• קחו את הכריך הימני העליון במשבצת שבשורה הראשונה מלמעלה ובעמודה השלישית משמאל.
• קחו את הכריך השמאלי התחתון במשבצת שבשורה הראשונה מלמעלה ובעמודה השלישית משמאל.
• קחו את הכריך הימני העליון במשבצת שבשורה השנייה מלמעלה ובעמודה השלישית משמאל.
• קחו את הכריך השמאלי התחתון במשבצת שבשורה השנייה מלמעלה ובעמודה השלישית משמאל.
• קחו את הכריך הימני התחתון במשבצת שבשורה השנייה מלמעלה ובעמודה השנייה משמאל.
• קחו את הכריך השמאלי העליון במשבצת שבשורה השנייה מלמעלה ובעמודה השנייה משמאל.

בסך הכול נלקחים $6$ כריכים, וזהו המספר המזערי, ולכן יש להדפיס 6.

קלט 2

2 2
NZ
ZN

פלט 2

-1 -1
-1 -1

הסבר

במקרה זה אי אפשר לקחת אף כריך.

קלט 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

פלט 3

10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10