1141 : โดมิโน (domino)
Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)
มีโดมิโนจำนวน N2 ตัว ตั้งเรียงเป็นรูปสี่เหลี่ยมจัตุรัสขนาด N×N อยู่บนพื้น โดมิโนเหล่านี้เป็นโดมิโนพิเศษที่สามารถผลักให้ล้มได้ในทุกทิศทาง

คุณต้องการผลักโดมิโนทั้งหมด M ครั้ง ในแต่ละครั้งจะผลักไปตามแนวของแถวหรือหลักของรูปสี่เหลี่ยมจัตุรัส โดยจะเริ่มผลักที่ตัวริมสุดของแถวหรือหลักนั้นเสมอ โดมิโนที่ถูกผลักจะล้มลง และหากมีโดมิโนตั้งอยู่ที่ตำแหน่งถัดไปในทิศทางที่ผลัก โดมิโนตัวนั้นก็จะล้มลงด้วย และจะล้มลงต่อกันไปเรื่อยๆ จนกว่าจะสุดแถว หรือมีโดมิโนที่ล้มอยู่แล้วตั้งอยู่ระหว่างทาง การล้มก็จะหยุดทันที

คุณต้องการทราบว่า ในการผลักแต่ละครั้ง จะมีโดมิโนล้มลงทั้งหมดกี่ตัว

งานของคุณ
จงเขียนโปรแกรมเพื่อรับขนาดของรูปสี่เหลี่ยมจัตุรัสและทิศทางในการผลักแต่ละครั้ง แล้วคำนวณหาจำนวนโดมิโนที่ล้มลงในการผลักแต่ละครั้ง

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ M (1 ≤ N ≤ 1,000,000,000; 1 ≤ M ≤ 100,000) แทนขนาดของรูปสี่เหลี่ยมจัตุรัส และจำนวนครั้งในการผลัก

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุตัวอักษร N, S, W หรือ E แล้วตามด้วยจำนวนเต็ม Xi แทนการผลักครั้งที่ i
  • หากอักษรตัวแรกคือ N หมายความว่า ผลักโดมิโนตามแนวหลักที่ Xi โดยเริ่มผลักที่ตัวในแถวบนสุด (ผลักในทิศลงมาด้านล่าง)
  • หากอักษรตัวแรกคือ S หมายความว่า ผลักโดมิโนตามแนวหลักที่ Xi โดยเริ่มผลักที่ตัวในแถวล่างสุด (ผลักในทิศขึ้นไปด้านบน)
  • หากอักษรตัวแรกคือ W หมายความว่า ผลักโดมิโนตามแนวแถวที่ Xi โดยเริ่มผลักที่ตัวในแถวซ้ายสุด (ผลักในทิศไปทางขวา)
  • หากอักษรตัวแรกคือ E หมายความว่า ผลักโดมิโนตามแนวแถวที่ Xi โดยเริ่มผลักที่ตัวในแถวขวาสุด (ผลักในทิศไปทางซ้าย)
ข้อมูลส่งออก
มีทั้งหมด N บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ N) ระบุจำนวนโดมิโนที่ล้มลงในการผลักครั้งที่ i

การให้คะแนน
30% ของข้อมูลทดสอบ จะมี N ≤ 1,000
60% ของข้อมูลทดสอบ จะมี N ≤ 100,000

ที่มา
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 4
N 2
W 3
S 2
N 1		 3
1
0
2
4 5
E 3
N 2
E 1
N 3
S 2		 4
2
2
0
1

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)