1071 : ระเบิด (bomb)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
    หลัง จากที่คุณทราบว่ากองกิ่งไม้ที่จะเผาบูชาไปนั้นทำให้เทพเจ้าทรงพระกริ้วจนถึง ขีดสุดแล้ว คุณและนักโบราณคดีจึงพยายามหลบหนีอย่างไม่คิดชีวิต แต่ทว่าเทพเจ้าแห่งตัวเลขตื่นขึ้นแล้ว และต้องการลงโทษคุณและนักโบราณคดีโดยการทิ้งระเบิดลงมายังโบราณสถานมาซู่
    ด้วย ความตกใจ คุณและผู้ร่วมคณะสำรวจจึงวิ่งออกมายังห้องโถงกว้างแห่งหนึ่ง ห้องโถงกว้างนี้มีพื้นที่เป็นสี่เหลี่ยมจัตุรัส กว้าง 1,000 หน่วยและยาว 1,000 หน่วย มุมล่างซ้ายของห้องอยู่ที่จุด (0, 0) และมุมบนขวาอยู่ที่จุด (1000 , 1000) ในระนาบสองมิติ
    เทพเจ้าแห่งตัวเลขจะทิ้งระเบิดลงมาทีละลูก ไปยังตำแหน่งบนพื้นห้องที่มีพิกัดตามแกน x และแกน y เป็นจำนวนเต็ม เมื่อมันตกมาถึงพื้นห้อง มันจะทำลายล้างทุกสิ่งที่อยู่รอบมันเป็นบริเวณสี่เหลี่ยมจัตุรัส ซึ่งมีความยาวด้านตามพลังทำลายล้างของระเบิด กล่าวคือหากลูกระเบิดซึ่งมีพลังทำลายล้าง R ตกถึงพื้นที่ตำแหน่ง (X, Y) มันจะทำลายล้างทุกสิ่งที่อยู่ในสี่เหลี่ยมจัตุรัสที่มีจุด (X - R, Y - R) เป็นมุมล่างซ้ายและจุด (X + R, Y + R) เป็นมุมบนขวา
    เคราะห์ดีที่คุณพอรู้คุณไสยมาบ้าง ก่อนนักโบราณคดีจะทำพิธีเผากิ่งไม้ คุณได้แปะยันต์ไว้ ณ ตำแหน่งต่างๆ บนพื้นห้องจำนวน N แผ่น โดยตำแหน่งที่คุณแปะจะมีพิกัดแกน x และแกน y เป็น จำนวนเต็มเสมอ ถ้ายันต์อยู่ในเขตการทำลายล้างของระเบิด มันจะถูกทำลาย (เพราะระเบิดจะทำลายล้างทุกสิ่ง) แต่ถ้าคุณไปยืนอยู่ ณ ตำแหน่งที่มียันต์แปะอยู่ และตำแหน่งนั้นไม่อยู่ในรัศมีทำลายล้างของระเบิด คุณจะปลอดภัยจากสะเก็ดระเบิดและภยันตรายอื่นๆ อีกมากมาย
    เพื่อ ทำให้โอกาสอยู่รอดของคณะสำรวจมีค่ามากที่สุด คุณต้องการทราบว่าระเบิดที่ตกลงมาแต่ละลูกจะทำลายยันต์ไปกี่แผ่น คุณมีเวลาไม่มาก เพราะตอนนี้ระเบิดกำลังร่วงลงมาแล้ว ช้าๆ

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

ข้อมูลนำเข้า
    บรรทัดแรกระบุจำนวนเต็ม N (1 ≤ N ≤ 100,000)  แทนจำนวนของยันต์ และจำนวนเต็ม M (1 ≤ M ≤ 100,000) แทนจำนวนของระเบิด
    อีก N บรรทัดต่อมามีข้อมูลของยันต์ N แผ่น แต่ละบรรทัดระบุจำนวนเต็ม x และ y (0 ≤ x, y ≤ 1,000) หมายความว่ายันต์แผ่นหนึ่งถูกแปะอยู่ที่จุด (x, y) เรารับประกันว่า ณ ตำแหน่งเดียวกันจะไม่มียันต์แปะอยู่มากกว่าหนึ่งแผ่น
    อีก M บรรทัดต่อมามีข้อมูลของระเบิด M ลูกตามลำดับที่เทพเจ้าทิ้งลงมา แต่ละบรรทัดมีจำนวนเต็ม X และ Y และ R (0 ≤ X, Y ≤ 1,000 และ 5 ≤ R ≤ 15) หมายความว่ามีระเบิดลูกหนึ่งถูกทิ้งลงมาที่จุด (X, Y) และระเบิดนั้นมีพลังทำลายล้าง R
    เทพเจ้าสามารถทิ้งระเบิดมากกว่าหนึ่งลูกลงที่จุดเดียวกันได้

ข้อมูลส่งออก
    มี M บรรทัด ในบรรทัดที่ i แสดงจำนวนเต็ม Bi แทนจำนวนยันต์ที่ระเบิดลูกที่ i ทำลาย

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

ที่มา: การแข่งขัน YTOPC Challenge เมษายน 2552
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 2
0 0
0 10
10 0
10 10
5 5
5 5 5
10 10 5
5
0
5 2
0 0
2 0
1 1
3 0
6 6
0 0 5
1 1 10
4
1

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

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