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 ในคำอธิบายโจทย์

ตัวอย่างเช่น หากต้องการหยิบแซนด์วิชทั้งสองชิ้นในช่องแถวที่ $2$ จากด้านบน คอลัมน์ที่ $2$ จากทางซ้าย สามารถหยิบตามลำดับต่อไปนี้ได้

• หยิบชิ้นขวาบนในช่องแถวที่ $1$ จากด้านบน คอลัมน์ที่ $3$ จากทางซ้าย
• หยิบชิ้นซ้ายล่างในช่องแถวที่ $1$ จากด้านบน คอลัมน์ที่ $3$ จากทางซ้าย
• หยิบชิ้นขวาบนในช่องแถวที่ $2$ จากด้านบน คอลัมน์ที่ $3$ จากทางซ้าย
• หยิบชิ้นซ้ายล่างในช่องแถวที่ $2$ จากด้านบน คอลัมน์ที่ $3$ จากทางซ้าย
• หยิบชิ้นขวาล่างในช่องแถวที่ $2$ จากด้านบน คอลัมน์ที่ $2$ จากทางซ้าย
• หยิบชิ้นซ้ายบนในช่องแถวที่ $2$ จากด้านบน คอลัมน์ที่ $2$ จากทางซ้าย

รวมต้องหยิบแซนด์วิช $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