และแล้วคำแนะนำที่ดีเยี่ยมก็โผล่มาดั่งอัศวินขี่ม้าขาว นักเลงคอมพิวเตอร์นิรนามผู้หนึ่งได้ช่วยให้คุณเจาะเข้าไปถึงโครงสร้างข้อมูลซึ่งมีลักษณะเป็นตาราง คุณทราบจากนักเลงคอมพิวเตอร์นิรนามว่ากุญแจสุดท้ายที่จะไขเข้าไปสู่ระบบฐานข้อมูลของ TOI.C อยู่ในกระจายอยู่ในตารางนี้ นั่นคือ รหัสซึ่งมีทั้งหมด N ตัว กระจายอยู่ตามแต่ละช่องในตารางนี้

            ถึงเวลาที่จะต้องไขพาสเวิร์ดให้ได้ ตารางข้อมูลนี้มีรูปเป็นสี่เหลี่ยมจัตุรัส ขนาด 1001 x 1001 หน่วย มุมล่างซ้ายของตารางอยู่ที่ช่อง (0,0) และมุมขวาบนของตารางอยู่ที่ช่อง (1000,1000) ในระนาบ 2 มิติ คุณไม่สามารถท่องเข้าไปในตารางข้อมูลนี้ได้ เนื่องจากการระบบการป้องกันภัยขั้นสูง

            สิ่งที่คุณทำได้คือการเจาะไปยังช่องใดช่องหนึ่งในตารางตำแหน่ง (X, Y) แล้วกระจายตัวเองออกไปรอบทิศด้วยพลังงาน K คุณจะได้รหัสพาสเวิร์ดทุกตัว ที่อยู่ภายในรูปสี่เหลี่ยมจัตุรัสที่มีจุด (X – K, Y – K) เป็นมุมล่างซ้าย และจุด (X + K, Y + K) เป็นมุมบนขวา ทั้งนี้เป็นไปได้ที่จะมีการแกะรหัสพาสเวิร์ดตัวเดิมเกิดขึ้นหลายครั้ง

            เคราะห์ร้ายที่คุณต้องเหนื่อยอีกครั้ง เมื่อพบว่าคุณสามารถเจาะตารางนี้ได้เพียง M ครั้งเท่านั้น

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

งานของคุณ

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

ข้อมูลนำเข้า

บรรทัดแรก ระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000) แทนจำนวนตัวของรหัส และจำนวนเต็ม M (1 ≤ M ≤ 1,000,000) แทนจำนวนครั้งของการเจาะ

อีก N บรรทัดถัดมา มีข้อมูลของรหัสทั้ง N ตัว โดยในบรรทัดที่ i + 1 ระบุจำนวนเต็ม X_i และ Y_i (0 ≤ X_i, Y_i ≤ 1,000) ซึ่งเป็นตำแหน่งช่องที่รหัสนั้นอยู่ในตาราง ทั้งนี้อาจมีรหัสสองตัวใดๆ อยู่ในตำแหน่งเดียวกันได้

อีก M บรรทัดต่อมา มีข้อมูลการเจาะตาราง โดยในบรรทัดที่ j + N + 1 มีจำนวนเต็ม X_j และ Y_j และ K_j (0 ≤ X_j, Y_j ≤ 1,000 และ 0 ≤ K_j ≤ 1,000) หมายความว่าในการเจาะตารางครั้งที่ j มีการเจาะที่ตำแหน่ง (X_j, Y_j) ด้วยพลังงาน K_j เนื่องจากคุณง่วงและเบลอ เป็นไปได้ที่คุณจะเจาะตารางซ้ำที่เดิมด้วยพลังงานเดิม

ข้อมูลส่งออก

มี M บรรทัด ในบรรทัดที่ j แสดงจำนวนเต็ม B_j แทนจำนวนรหัสที่ทราบมาจากการเจาะตารางครั้งที่ j

การให้คะแนน

50% ของชุดข้อมูลทดสอบมีค่า N, M ≤ 10,000 และในทุกชุดข้อมูลทดสอบมีค่า N, M ≤ 1,000,000

โจทย์โดย: พศิน มนูรังษี