يشارك JOI في الحفل الاجتماعي لـ IOI. في الحفل، وُضعت شطائر على شبكة من الخلايا المربعة تتكون من $R$ صفوف و$C$ أعمدة. كل شطيرة على شكل مثلث قائم متساوي الساقين، طول كل من ساقيه يساوي طول ضلع الخلية. وتوجد في كل خلية شطيرتان يتلامس وترهما. يوضح الشكل التالي مثالًا لترتيب الشطائر.

الشكل 1. مثال لترتيب الشطائر

لا يمكن أخذ شطيرة إذا تحقق الشرطان التاليان معًا:

• وترها يلامس شطيرة أخرى لم تؤخذ بعد.
• واحد على الأقل من ضلعيها الآخرين يلامس شطيرة أخرى لم تؤخذ بعد.

يمكن أخذ أي شطيرة لا تحقق هذين الشرطين معًا.

نسمي الحالة التي لم تؤخذ فيها أي شطيرة الحالة الابتدائية. انطلاقًا من الحالة الابتدائية، قد يلزم أخذ بعض الشطائر الأخرى قبل التمكن من أخذ شطيرة معينة. وقد توجد شطائر يستحيل أخذها، بحسب ترتيب الشطائر.

يريد JOI أن يأكل الشطيرتين الموجودتين في خلية واحدة. ولم يقرر بعد الخلية التي سيأكل شطائرها.

يريد معرفة أقل عدد من الشطائر التي يجب أخذها، انطلاقًا من الحالة الابتدائية، لأخذ الشطيرتين الموجودتين في خلية معينة.

المهمة

عندما يُعطى ترتيب الشطائر، اكتب برنامجًا يحدد لكل خلية ما إذا كان من الممكن أخذ شطيرتيها كلتيهما عن طريق أخذ بعض الشطائر انطلاقًا من الحالة الابتدائية. وإذا كان ذلك ممكنًا، فاحسب أقل عدد من الشطائر التي يجب أخذها. تُحتسب الشطيرتان المطلوبتان أيضًا ضمن هذا العدد.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على عددين صحيحين $R,C$ يفصل بينهما فراغ. وهما يدلان على أن الشطائر مرتبة على شبكة من الخلايا المربعة تتكون من $R$ صفوف و$C$ أعمدة.
• يحتوي السطر $i$ ($1 \le i \le R$) من الأسطر $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